Page 293 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes In the case where the weight of Y is less than the weight of Y we can conclude that Y is not
2 1 1
a minimum spanning tree, and the assumption that there exist edges e,f with w(e) < w(f) is
incorrect. And therefore Y is a minimum spanning tree (equal to Y or with a different edge set,
1
but with same weight).
Figure 14.12: Step by Step Representation of kruskal’s Algorithm
2
(0) v 0 v 1
5 F = {{V ), (V ), {V }, (V ))
0
MST = {} 1 3 4
1 6 1 v 2 Q = {{V , V ), (V , V ), (V , V ),
0
4
1
3
4
3
3
v v {V , V ), {V , V ), {V , V ), {V , V )
4
2
1
1
0
2
3
1
4 3
1
2
(1) v 0 v 1 (V , V ) = ExtractMin
0
4
5 (Q) – ACCEPTED
F = {(V , V ), (V ), (V ), {V )}
4
0
1 1 v MST = {(V , V )} 1 2 3
6 2 0 4
Q = {(V , V ), (V , V ),
3
4
3
1
3 (V , V ), (V , V ), (V , V ), (V , V )
v v 0 1 2 3 1 2 1 4
4 3
1
2
(2) v v (V , V ) = ExtractMin (Q)-Accepted
0 1 1 3
5 F= {(V , V ), {V , V }, {V }}
3
1
4
0
2
MST = {(V , V ), (V , V )}
0
1
4
3
1 6 1 v 2 Q = {(V , V ),
4
3
(V , V ), (V , V ), (V , V )
1
0
3 (V , V ) 2 3 1 2
v v 1 4
4 3
1
(3) v 0 2 v 1
5 (V , V ) = ExtractMin (Q)-Accepted
4
3
F= {(V , V , V , V }, {V }}
0
2
1
3
4
1 6 1 v 2 MST = {(V , V ), (V , V ), (V , V )}
4
1
3
3
4
0
Q = {(V , V ), (V , V ), (V , V ) , (V , V )}
1
1
4
3
2
0
2
1
3
v v
4 3
1
(4) v 0 2 v 1
5 (V , V ) = ExtractMin (Q)--Rejected
0
1
F= {{V , V , V , V }, {V }}
1 1 v 0 1 3 4 2
6 2 MST = {(V , V ), (V , V ), (V , V )}
3
4
1
3
4
0
Q = {(V , V ), (V , V ), (V , V )
3 2 3 1 2 1 4
v 4 v 3
1
(5) v 2 v
0 1 (V , V ) = ExtractMin (Q)--Accepted
2
3
5
F= {{V , V , V , V , V },
0
1
2
3
4
1 6 1 v 2 MST = {(V , V ), (V , V ), (V , V )
3
4
4
1
3
0
(V , V )}
2
3
Q = {(V , V ), (V , V )},
3 1 2 1 4
v v
4 3
1
6. The algorithm continues until Q becomes empty, but since the forest has become one tree, all
remaining edges in Q will be rejected and no change will happen to MST.
288 LOVELY PROFESSIONAL UNIVERSITY