We help IT Professionals succeed at work.

Prims and Kruskals algorithm

mustish1
mustish1 asked
on
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
Comment
Watch Question

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

Author

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

Author

Commented:
Technical Development Lead
Commented:
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.

Author

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

Author

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?
Neil RussellTechnical Development Lead
Commented:
Do you know Java?
This article includes lots of Java code examples to help explain the workings.

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

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

Author

Commented:
ONE MORE

DC is the shortest arc with length 2

Author

Commented:

Author

Commented:
Can experts please tell me if i did right
Neil RussellTechnical Development Lead
Commented:
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
Neil RussellTechnical Development Lead
Commented:
Sorry thats
d-g OR h-g
AB completes a circuit for ABCDA.

Tom

Author

Commented:

Author

Commented:
is this is correct?
Neil RussellTechnical Development Lead

Commented:
No you still have loops. I gave you the solution above in #37228420
Can you see why if you draw it?
Neil RussellTechnical Development Lead
Commented:
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
Neil RussellTechnical Development Lead

Commented:

An easier to visualize example. Better example viually

Author

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

Why you start with 3 instead of 1 ?
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.