Page 295 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 13. end
14. end
15. end

Proof of Correctness

Let P be a connected, weighted graph. At every iteration of Prim’s algorithm, an edge must be
found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected,
there will always be a path to every vertex. The output Y of Prim’s algorithm is a tree, because the
edge and vertex added to Y are connected. Let Y be a minimum spanning tree of P. If Y = Y then
1 1
Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction

of Y that is not in Y , and V be the set of vertices connected by the edges added before e. Then
1
one endpoint of e is in V and the other is not. Since Y is a spanning tree of P, there is a path in Y
1
1
joining the two endpoints. As one travels along the path, one must encounter an edge f joining
a vertex in V to one that is not in V. Now, at the iteration when e was added to Y, f could also
have been added and it would be added instead of e if its weight was less than e. Since f was not
added, we conclude that
w(f) 24 w(e).
12
Let Y be the graph obtained by removing f and adding e from Y . It is easy to show that Y is
1
2
2
connected, has the same number of edges as Y , and the total weights of its edges is not larger
1
than that of Y , therefore it is also a minimum spanning tree of P and it contains e and all the
1
edges added before it during the construction of V. Repeat the steps above and we will eventually
obtain a minimum spanning tree of P that is identical to Y . This shows Y is a minimum spanning
1
tree.
Figure 14.14: Step-by-Step Representation of Prim’s Algorithm
(0) v 0 v 1
2
0 d v known d p
5 v v
v 0 F 0 0
1 1 d v v F d 0
6 2 1
v 2 F d 0
3 v 3 F d 0
d d v 4 F d 0
1
v v Q = {v , v , v , v , v }
4 3
0 1 2 3 4
(1) v 0 v 1
2
0 2 v known d p
5 v v
v 0 T 0 0
1 1 d v v F 2 v
6 2 1 0
v 2 F d 0
3 v 3 F d 0
1 d v 4 F 1 v 0
1
v v Q = {v , v , v , v , v }
4 3
4 1 2 3 4
(2) v 0 v 1
2
0 2 v known d p
5 v v
v 0 T 0 0
1 6 1 d v 2 v 1 F 2 v 0
v 2 F d 0
3 v 3 F 1 v 4
1 1 v 4 T 1 v 0
1
v v Q = {v , v , v }
4 3 Contd...
3 1 2
290 LOVELY PROFESSIONAL UNIVERSITY