Minimum Spanning Tree of a Graph Solutions

[whoareyou]

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

[Dreadnought]

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]

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]

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]

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]

whoareyou @ Tue Feb 25, 2014 11:26 pm wrote:

only one minimal solution
...
SOLUTION__S__

Doesn't this answer the question?

[whoareyou]

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.