2.5 Kruskal's algorithm

Part 2 · Trees and paths · Chapter 2 · Chapter 2: Spanning trees · Lecture notes, volume 2 (PDF) · Exercises: Spanning trees · App: Minimum spanning trees: Kruskal and Prim

Algorithm: Kruskal's algorithm

Input: a connected undirected graph \(G=(V,E)\) with weights \(w_e\)

Output: a minimum spanning tree \(F\)

1Step 0 (initialization). Sort the edges by non-decreasing weight, \(w_{e_1} \le w_{e_2} \le \dots \le w_{e_m}\), and set \(F:=\emptyset\).

2Step 1 (scan). For \(k=1,2,\dots,m\): if the endpoints of \(e_k\) are in different components of \((V,F)\), set \(F:=F \cup \{e_k\}\); otherwise reject \(e_k\).

3 If \(|F|=n-1\), STOP.

• An edge is accepted if it joins two different components of \((V,F)\), and rejected if it would close a cycle. The components of \((V,F)\) start as the \(n\) single vertices and merge at every acceptance.

• In this module, edges of equal weight are scanned in lexicographic order of \(\{u,v\}\), with \(u<v\).

Theorem 2.10: correctness of Kruskal's algorithm

Kruskal's algorithm stops with \(|F|=n-1\), and \(F\) is a minimum spanning tree.

Proof

We show that every accepted edge \(e_k=\{u,v\}\) is a choice of Step 2 of the generic greedy algorithm. Let \(S\) be the component of \((V,F)\) that contains \(u\), just before \(e_k\) is accepted: \(v \notin S\), and no edge of \(F\) crosses \(\delta(S)\).

1. Let \(e_h \in \delta(S)\) with \(h<k\). When \(e_h\) was scanned it was not accepted, since \(F \cap \delta(S)=\emptyset\); so its endpoints were in the same component then, and they still are, because components only merge. This contradicts \(e_h \in \delta(S)\).

2. Hence every edge of \(\delta(S)\) is some \(e_h\) with \(h \ge k\), and \(w_{e_h} \ge w_{e_k}\): \(e_k\) has minimum weight in \(\delta(S)\).

3. If the scan ended with \(|F|<n-1\), the forest \((V,F)\) would have two components joined by an edge of \(G\), and that edge would have been accepted when scanned, by the argument of point 1.

By Theorem 2.9, \(F\) is a minimum spanning tree. □

2.5.1 Implementation and running time

• The components of \((V,F)\) are kept in a union–find structure: every vertex \(v\) stores the label \(\mathit{comp}(v)\) of its component, and every component stores the list of its vertices and its size.

• Testing whether \(u\) and \(v\) are in different components is the comparison \(\mathit{comp}(u) \neq \mathit{comp}(v)\), in \(O(1)\) time. Merging two components relabels the vertices of the smaller one (union by size).

Theorem 2.11: running time of Kruskal's algorithm

With the union–find structure by labels and union by size, Kruskal's algorithm runs in \(O(m\log n)\) time.

Proof

1. Sorting the edges takes \(O(m\log m)\) time; since \(m \le n^2\), \(\log m \le 2\log n\) and this is \(O(m\log n)\).

2. The scan performs \(m\) tests, each in \(O(1)\) time.

3. When a vertex is relabelled, its component merges with one at least as large, so the size of its component at least doubles. The size never exceeds \(n\), so each vertex is relabelled at most \(\log_2 n\) times: all the merges take \(O(n\log n)\) time.

\(G\) is connected, so \(n-1 \le m\), and the total is \(O(m\log n+n\log n)=O(m\log n)\). □

• The running time is dominated by the sorting. With the union–find structure by trees, with union by rank and path compression, the scan takes almost linear time; the bound stays \(O(m\log n)\) because of the sorting.

• The algorithm uses only comparisons between weights: any increasing transformation of the weights gives the same tree.

2.5.2 Kruskal's algorithm on the reference graph

Example 2.7: Kruskal's algorithm

We run Kruskal's algorithm on the weighted reference graph. The edges in order of weight are \(\{1,3\},\{4,5\},\{2,3\},\{1,2\},\{3,4\},\{2,4\},\{5,6\},\{3,5\},\{4,6\}\). Each row is one scanned edge, with the components of \((V,F)\) after the step:

\(k\)	edge \(e_k\)	\(w_{e_k}\)	decision and components of \((V,F)\)
\(1\)	\(\{1,3\}\)	\(1\)	accept: \(\{1,3\},\{2\},\{4\},\{5\},\{6\}\)
\(2\)	\(\{4,5\}\)	\(2\)	accept: \(\{1,3\},\{2\},\{4,5\},\{6\}\)
\(3\)	\(\{2,3\}\)	\(3\)	accept: \(\{1,2,3\},\{4,5\},\{6\}\)
\(4\)	\(\{1,2\}\)	\(4\)	reject (\(1\) and \(2\) are both in \(\{1,2,3\}\))
\(5\)	\(\{3,4\}\)	\(5\)	accept: \(\{1,2,3,4,5\},\{6\}\)
\(6\)	\(\{2,4\}\)	\(6\)	reject (\(2\) and \(4\) are both in \(\{1,2,3,4,5\}\))
\(7\)	\(\{5,6\}\)	\(7\)	accept: \(\{1,2,3,4,5,6\}\); \(|F|=5\), STOP

The algorithm stops after \(7\) of the \(9\) edges, with \(F=\{\{1,3\},\{4,5\},\{2,3\},\{3,4\},\{5,6\}\}\) of weight \(18\): the tree \(\tilde{F}\) of Example 2.2. The figure shows, on each tree edge, its weight and in brackets the step \(k\) of its acceptance.

• The rejected edges \(\{1,2\}\) and \(\{2,4\}\) are the heaviest edges of the cycles \(1,2,3\) and \(2,3,4\), as the cycle property predicts; the edges \(\{3,5\}\) and \(\{4,6\}\) are never scanned.

Kruskal's algorithm scans the edges by non-decreasing weight and accepts those that join two components; with union–find it runs in \(O(m\log n)\) time, dominated by the sorting.

---

Next: 2.6 Prim's algorithm