Minimum Spanning Tree of a Graph Solutions
Author 
Message 
whoareyou

Posted: 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:
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







Sponsor Sponsor



Dreadnought

Posted: 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} 





whoareyou

Posted: 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. 





Dreadnought

Posted: Tue Feb 25, 2014 10:44 pm Post subject: Re: Minimum Spanning Tree of a Graph Solutions 


whoareyou wrote: I think you meant {AB, A C, BG, CE, DE, FG} but thanks, those are the two solutions the program reported as well.
Ya, that's what I meant, woops! 





whoareyou





Tony

Posted: 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? 
Tony's programming blog. DWITE  a programming contest. 




whoareyou

Posted: 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. 






