Prims and Kruskals algorithm

Hi guys: I give the name on each vertax a,b,c,d,e,f,g,h. Can any one please tell me how to find a minimal spanning tree and compute its total weight on this diagram?

Thanks.

qq2.jpg
mustish1Asked:
Who is Participating?
 
Neil RussellTechnical Development LeadCommented:
There is an excellant article from the University of california HERE that will lead you to your answer.

It is often far better to learn from your own experimentation than to be given just the answer.

0
 
tliottaCommented:
Edges cd and ce have no weights that I can see. Is that intended or does it indicate zero or 'unknown'? Is fh weighted 5 or 8? (I can't quite decide.)

Tom
0
 
mustish1Author Commented:
sorry
fh=5
cd=2
ce=8
0
Cloud Class® Course: Microsoft Exchange Server

The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

 
mustish1Author Commented:
0
 
mustish1Author Commented:
i want to do b ymyself. please let me know if i go wrong
0
 
mustish1Author Commented:
BC is the shortest arc with length 1.

so now BA and BE
BE is the shortest arc with length 2.

so now AC and AD
AD is the shortest arc with length 1.

AC create loop or circuit so we cant use it.

am i doing right?
0
 
Neil RussellTechnical Development LeadCommented:
Do you know Java?
This article includes lots of Java code examples to help explain the workings.

http://algs4.cs.princeton.edu/43mst/
0
 
mustish1Author Commented:
so now DG and DF
DG is the shortest arc with length 8

DF is the shortest arc with length 7

EF is the shortest arc with length 3
FH is the shortest arc with length 5
GH is the shortest arc with length 6

I THINK REST OF THEM CREATE CIRCUIT

0
 
mustish1Author Commented:
ONE MORE

DC is the shortest arc with length 2
0
 
mustish1Author Commented:
0
 
mustish1Author Commented:
Can experts please tell me if i did right
0
 
Neil RussellTechnical Development LeadCommented:
Nope you have loops/cycles
a-d
d-c
c-b
b-e
e-f
f-h
d-d OR h-g

Is the MST
0
 
Neil RussellTechnical Development LeadCommented:
Sorry thats
d-g OR h-g
0
 
tliottaCommented:
AB completes a circuit for ABCDA.

Tom
0
 
mustish1Author Commented:
0
 
mustish1Author Commented:
is this is correct?
0
 
Neil RussellTechnical Development LeadCommented:
No you still have loops. I gave you the solution above in #37228420
Can you see why if you draw it?
0
 
Neil RussellTechnical Development LeadCommented:
From any ONE vertex (x) there should and can only be one path to any other vertex (y)
You have a-b-e-f-d-a
d-g-h-f-d
etc
LOOPS
0
 
Neil RussellTechnical Development LeadCommented:

An easier to visualize example. Better example viually
0
 
mustish1Author Commented:
> I gave you the solution above in #37228420

Why you start with 3 instead of 1 ?
0
 
phoffricCommented:
Actually you can start with any vertex. But, it is possible that when starting from different vertices, you will get multiple solutions all having the same minimum value.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.