Page 292 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

Algorithm Notes

Let G = (V, E) which is represented by an adjacency list Adj. Some support data structures:
1. F is the forest — a set of all (partial) trees.

2. MST is the minimum spanning tree, represented by a set of edges.
3. Q is a priority queue of edges.

Kruskal(G)

1. Let F be a set of singleton set of all vertices in G.
2. MST <- {}

3. Q <- E
4. while Q not empty do
5. (u, v) <- ExtractMin(Q) // Q is modifi ed
6. if FIND-SET(u) != FIND-SET(v) then // FIND-SET(i) returns the set in F
// which vertex i belongs to.
// This effectively does cycle check.
// If ACCEPTED,
7. begin
8. merge(FIND-SET(u),FIND-SET(v)) in F

9. MST <- MST Union {(u, v)}
10. end
11. return MST.

Proof of Correctness

Let P be a connected, weighted graph and let Y be the subgraph of P produced by the algorithm.
Y cannot have a cycle, since the last edge added to that cycle would have been within one subtree

and not between two different trees. Y cannot be disconnected, since the first encountered edge
that joins two components of Y would have been added by the algorithm. Thus, Y is a spanning
tree of P.
It remains to show that the spanning tree Y is minimal:
Let Y be a minimum spanning tree. If Y = Y then Y is a minimum spanning tree. Otherwise, let e
1 1

be the first edge considered by the algorithm that is in Y but not in Y . Y U e has a cycle, because
1
1
you cannot add an edge to a spanning tree and still have a tree. This cycle contains another edge
f which at the stage of the algorithm where e is added to Y, has not been considered. This is
because otherwise e would not connect different trees but two branches of the same tree. Then Y
2
= Y U e/f is also a spanning tree.
1
Its total weight is less than or equal to the total weight of Y . This is because the algorithm visits
1
e before f and therefore w(e) £ w(f) . If the weights are equal, we consider the next edge e which
is in Y but not in Y . If there is no edge left, the weight of Y is equal to the weight of Y although
1
1
they consist of a different edge set and Y is also a minimum spanning tree.

LOVELY PROFESSIONAL UNIVERSITY 287