Generate Min-Cost Tree using Kruskal

For each some Graph , may need to find out the "Minimum cost " way to build .

for this graph , Now need to find out the min-cost tree .

This method is named as Kruskal :

Now we get {v0,v1,v3,v4,v5,v6,v7,v8} 9 points .and if weconsider the value between each point standing for the cost ,now let's make the costminimum and make it through.

Step 1: get all edges and sort

7(v7,v4),8(v2,v8),10(v1,v0),11(v0,v5),12(v1,v8),16(v1,v6),

16(v3,v7),17(v6,v5),18(v2,v1),19(v6,v7),20(v3,v4),21(v8,v3),

22(v2,v3),26(v5,v4)

Step 2:

Now let's connect all points by the order just sorted .

Note: before do this , prepare 9 Sets to store each point group.

In beginning , 9 Sets should be like :

{v0},{v1},{v2},{v3},{v4},{v5},{v6},{v7},{v8},{v9}

Now Do it .

Let's start with (v4,v7).

Sets(8 sets) :

{v0},{v1},{v2},{v3},{v4,v7},{v5},{v6},{v8}

(v2,v8)

Sets(7 sets):

{v0},{v1},{v2,v8},{v3},{v4,v7},{v5},{v6}

Continue , now (v1,v0)

Sets(6 sets):

{v0,v1},{v2,v8},{v3},{v4,v7},{v5},{v6}

all what we should remember is :

1.new added 2 points shall not be exist in the same set.

e.g. now I want to add {v2,v8}, whichis not allowed ,as they(v2,v8) are already in the same set.

2.Once we get only 1 set , we stop .

Now Let's continue.

Add (v0,v5)

Now Sets(5 sets):

{v0,v1,v5},{v2,v8},{v3},{v4,v7},{v6}

Add (v1,v8), As points already added, We just need to union these twosets.

Now Sets(4 sets):

{v0,v1,v5,v2,v8},{v3},{v4,v7},{v6}

Next ,Add(v1,v6)

Now Sets(3 SETS):

{v0,v1,v5,v2,v8,v6},{v3},{v4,v7}

Next (V3,V7)

Sets(2 SETS):

{v0,v1,v5,v2,v8,v6},{V3,v4,v7}

Next (v5,v6),Because these are in the same set already ,so jump to next directly.

Same reason for Next (V1,V2) ,These are in the same set.

Ok, Now (V6,V7)

Sets (1 set):

{v0,v1,v5,v2,v8,v6,V3,v4,v7}

Finish.