Discrete Mathematics for Computer Science

Spanning Trees 375

INPUT: Connected graph G = (V, E)

OUTPUT: A spanning tree T of G

V(T) = V(G) /* Initialize */

E(T) = 0

for each e E E(G) do

if ({e} U E(T) is acyclic) then

E(T) = E(T) U {e}

6.11.2 Correctness of Kruskal's Algorithm

To show that Kruskal's algorithm is correct, it must be shown that the subgraph T formed
by the algorithm is a spanning subgraph for G and that T is both connected and acyclic. T
is clearly a spanning subgraph, because V(T) is defined to be V(G). Since no edge is ever
added to T that forms a cycle, T is acyclic, but it remains to be shown that T is connected.
Suppose T is not connected. Let u and v be vertices that lie in different components of T.
Since G is connected, there must be a path P in G from u to v. Traveling along P from
u toward v, let e be the first edge that leaves the component of T containing u and enters
some other component of T. Since e bridges two components of T, e does not belong to

T. Since the endpoints of e are not joined by any path in T, E(T) U e is acyclic. Thus,

when e was considered in the execution of the algorithm, E(T) U e was acyclic; therefore,
e was added to E(T). This contradicts e ý E(T). Since assuming T is not connected led
to a contradiction, T must be connected.
The algorithm will be clarified by applying the proof to the example shown in Figure
6.35. The edges listed in each part of the diagram indicate the tree edges (solid lines) and
the edges that form cycles (dashed line) and, thus, are not included in T.

(1,2)

E(G) (3,4)

(1,2) (2,5) (1,4)

(3,4) (5,6) (1,6) 1 (2,3) 1

(2, 5)

(5, 6)

(1,6) 5 3 5 3 5 3

(1,4)

(2,3) 4 4

(4, 5)

(3,6) (4,5) 1 (3,6) 1

6 2 6 2 6 2

5 L' 3 5 * 3 5 3

4 4 4

T

Figure 6.35 Finding a spanning tree.