Computer Science Canada

Minimum Spanning Tree of a Graph Solutions
Author:  whoareyou [ Tue Feb 25, 2014 8:22 pm ]
Post subject:  Minimum Spanning Tree of a Graph Solutions
Hello,

I recently wrote a program that implements a slightly modified version of Prim's Algorithm and it seems to work correctly. However, I am doubtful because my prof claims that this certain tree has only 1 minimal solution but my program gives quite a few different solutions (edit: 2 different solutions). Note that a different solution means that different edges are used to visit every node. Using the same edges in a different order is not a different solution. Can someone please confirm this:

GRAPH:
Posted Image, might have been reduced in size. Click Image to view fullscreen.

SOLUTIONS:
code:

A -> B: 2
A -> C: 3
C -> E: 1
B -> G: 4
G -> F: 2
E -> D: 5

TOTAL DISTANCE: 17

B -> A: 2
A -> C: 3
C -> E: 1
B -> G: 4
G -> F: 2
E -> D: 5

TOTAL DISTANCE: 17

C -> E: 1
C -> A: 3
A -> B: 2
E -> F: 4
F -> G: 2
E -> D: 5

TOTAL DISTANCE: 17

D -> E: 5
E -> C: 1
C -> A: 3
A -> B: 2
E -> F: 4
F -> G: 2

TOTAL DISTANCE: 17

E -> C: 1
C -> A: 3
A -> B: 2
B -> G: 4
G -> F: 2
E -> D: 5

TOTAL DISTANCE: 17

F -> G: 2
F -> E: 4
E -> C: 1
C -> A: 3
A -> B: 2
E -> D: 5

TOTAL DISTANCE: 17

G -> F: 2
G -> B: 4
B -> A: 2
A -> C: 3
C -> E: 1
E -> D: 5

TOTAL DISTANCE: 17
Author:  Dreadnought [ Tue Feb 25, 2014 9:25 pm ]
Post subject:  Re: Minimum Spanning Tree of a Graph Solutions
I agree, there are two different solutions to this tree.

1) E(T) = {AB, AC, CE, DE, EF, FG}
2) E(T) = {AB, AB, BG, CE, DE, FG}
Author:  whoareyou [ Tue Feb 25, 2014 10:11 pm ]
Post subject:  Re: Minimum Spanning Tree of a Graph Solutions
Dreadnought @ Tue Feb 25, 2014 9:25 pm wrote:

2) E(T) = {AB, AB, BG, CE, DE, FG}


I think you meant {AB, AC, BG, CE, DE, FG} but thanks, those are the two solutions the program reported as well. Very Happy
Author:  Dreadnought [ Tue Feb 25, 2014 10:44 pm ]
Post subject:  Re: Minimum Spanning Tree of a Graph Solutions
whoareyou wrote:
I think you meant {AB, AC, BG, CE, DE, FG} but thanks, those are the two solutions the program reported as well. Very Happy

Ya, that's what I meant, woops!
Author:  whoareyou [ Tue Feb 25, 2014 11:26 pm ]
Post subject:  RE:Minimum Spanning Tree of a Graph Solutions
Could somebody also confirm that there is only one minimal solution to this graph? My prof seems to hint that there may be more than one solution but my program gives the same solution every time (perhaps he got them switched with the one before? or my program is wrong Sad ):

GRAPH:
Posted Image, might have been reduced in size. Click Image to view fullscreen.

SOLUTIONS:
code:
A -> B: 3
A -> C: 3
C -> D: 3
B -> H: 6
H -> F: 3
H -> I: 4
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

B -> A: 3
A -> C: 3
C -> D: 3
B -> H: 6
H -> F: 3
H -> I: 4
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

C -> A: 3
C -> D: 3
A -> B: 3
C -> E: 6
E -> G: 4
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

D -> C: 3
C -> A: 3
A -> B: 3
C -> E: 6
E -> G: 4
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

E -> G: 4
E -> C: 6
C -> A: 3
C -> D: 3
A -> B: 3
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

F -> H: 3
H -> I: 4
H -> B: 6
B -> A: 3
A -> C: 3
C -> D: 3
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

G -> E: 4
E -> C: 6
C -> A: 3
C -> D: 3
A -> B: 3
B -> H: 6
H -> F: 3
H -> I: 4

TOTAL DISTANCE: 32

H -> F: 3
H -> I: 4
H -> B: 6
B -> A: 3
A -> C: 3
C -> D: 3
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32

I -> H: 4
H -> F: 3
H -> B: 6
B -> A: 3
A -> C: 3
C -> D: 3
C -> E: 6
E -> G: 4

TOTAL DISTANCE: 32
Author:  Tony [ Wed Feb 26, 2014 3:36 am ]
Post subject:  Re: RE:Minimum Spanning Tree of a Graph Solutions
whoareyou @ Tue Feb 25, 2014 11:26 pm wrote:
only one minimal solution
...
SOLUTION__S__

Doesn't this answer the question?
Author:  whoareyou [ Wed Feb 26, 2014 8:40 am ]
Post subject:  Re: RE:Minimum Spanning Tree of a Graph Solutions
Tony @ Wed Feb 26, 2014 3:36 am wrote:
whoareyou @ Tue Feb 25, 2014 11:26 pm wrote:
only one minimal solution
...
SOLUTION__S__

Doesn't this answer the question?


No, the output just shows the path starting from each node but I've analyzed each of the paths and they're all the same so I just want some confirmation that there is only one minimal spanning tree since my prof seems to hint that may be the case. Or my algorithm could be messed up.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy