Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Minimum Spanning Tree of a Graph Solutions
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
whoareyou




PostPosted: 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
Sponsor
Sponsor
Sponsor
sponsor
Dreadnought




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




PostPosted: 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
Dreadnought




PostPosted: 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!
whoareyou




PostPosted: 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
Tony




PostPosted: 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?
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
whoareyou




PostPosted: 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.
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 7 Posts ]
Jump to:   


Style:  
Search: