We help IT Professionals succeed at work.

# Prims and Kruskals algorithm

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

## View Solutions Only

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

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

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

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

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

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

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

Commented:
ONE MORE

DC is the shortest arc with length 2

Commented:

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

Tom

Commented:

Commented:
is this is correct?

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