6.4 MINIMUM SPANNING TREE ALGORITHM 159■ 6.4.2 The Kruskal Algorithm
Where the Dijkstra-Prim algorithm began at a particular node and built the
minimum spanning tree outward, Kruskal’s algorithm concentrates instead on
the edges of the graph.
In this algorithm, we begin with an empty spanning tree and add edges in
order of increasing weight until all nodes are connected to the graph. If we run
out of edges before all of the nodes are connected, the original graph wasn’t
connected, and the result we have generated is the MSTs of each of the con-
nected components of the original graph.
We begin in Fig. 6.6(a) with the same graph that we used for the Dijkstra-
Prim algorithm. In this case, we first add the edge with the lowest weight,
which is the one between nodes D and F, giving the partial results in Fig.
6.6(b).
The edge with weight 2 is added next (Fig. 6.6(c)) between the nodes A and
B, and then the edge with weight three is added, giving us Fig. 6.6(d).
The edges with weights of 4 and 5 are next added to our result, as you can
see in Figs. 6.6(e) and 6.6(f). Only node G is still unconnected. The next edges
to consider are those with a weight of 6.
Of the four edges with a weight of 6, two are discarded because they would
form a cycle with edges already part of the MST. The edge between nodes C
and F would form a cycle that includes node A, and the edge between node B
and D would form a cycle that includes nodes A and F. The other two nodes
are both good alternatives, and depending on the one chosen, we get the MST
in either Fig. 6.6(g) or Fig. 6.6(h).
A BF GC D E(^47)
7
6
2
6
6
6
1
58
3
A B
F G
C D E
1
■FIGURE 6.6A
The original graph
■FIGURE 6.6B
First edge added