Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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

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.

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, AC, BG, CE, DE, FG} but thanks, those are the two solutions the program reported as well.

Ya, that's what I meant, woops!
whoareyou

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

GRAPH:

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
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__

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__