# 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
###### Who is Participating?

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

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

Author Commented:
sorry
fh=5
cd=2
ce=8
0

Author Commented:
0

Author Commented:
i want to do b ymyself. please let me know if i go wrong
0

Author Commented:
BC is the shortest arc with length 1.

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

AD is the shortest arc with length 1.

AC create loop or circuit so we cant use it.

am i doing right?
0

Do you know Java?
This article includes lots of Java code examples to help explain the workings.

http://algs4.cs.princeton.edu/43mst/
0

Author 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

Author Commented:
ONE MORE

DC is the shortest arc with length 2
0

Author Commented:
0

Author Commented:
Can experts please tell me if i did right
0

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

Sorry thats
d-g OR h-g
0

Commented:
AB completes a circuit for ABCDA.

Tom
0

Author Commented:
0

Author Commented:
is this is correct?
0

No you still have loops. I gave you the solution above in #37228420
Can you see why if you draw it?
0

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

An easier to visualize example.
0

Author Commented:
> I gave you the solution above in #37228420

0

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