Skip to content

2.4 The generic greedy 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

  • The cut property suggests building a minimum spanning tree one edge at a time: the current set \(F\) is always contained in some minimum spanning tree, and the next edge is the lightest edge of a cut not crossed by \(F\).

Algorithm: Generic greedy algorithm for the MST

Input: a connected undirected graph \(G=(V,E)\) with weights \(w_e\)
Output: a minimum spanning tree \(F\)
1Step 0 (initialization). Set \(F:=\emptyset\).
2Step 1 (stopping test). If \(|F|=n-1\), STOP.
3Step 2 (augmentation). Choose a cut \(\delta(S)\) with \(F \cap \delta(S)=\emptyset\), and add to \(F\) an edge of minimum weight in \(\delta(S)\). Go to Step 1.

Theorem 2.9: correctness of the generic greedy algorithm

At every iteration of the generic greedy algorithm a cut as in Step 2 exists and is nonempty, and \(F\) is contained in some minimum spanning tree. At the end, \(F\) is a minimum spanning tree.

Proof

By induction on the iterations; \(F=\emptyset\) is contained in every minimum spanning tree.

  1. If \(|F|<n-1\), the graph \((V,F)\) is a forest (a subset of a tree) with \(n-|F| \ge 2\) components. Let \(S\) be one of them: no edge of \(F\) crosses \(\delta(S)\), and \(\delta(S) \neq \emptyset\) because \(G\) is connected.

  2. By the cut property (Theorem 2.6(a)), the new set \(F \cup \{e\}\) is still contained in some minimum spanning tree.

  3. When \(|F|=n-1\), \(F\) is contained in a minimum spanning tree \(T^\star\) with \(n-1\) edges, so \(F=T^\star\). □

  • The added edge \(e=\{u,v\}\) has \(u \in S\) and \(v \notin S\), and no edge of \(F\) crosses \(\delta(S)\): \(u\) and \(v\) are in different components of \((V,F)\), so \(e\) does not close a cycle.

  • The algorithms of Kruskal and of Prim are two ways of choosing the cut in Step 2.

Adding, \(n-1\) times, the lightest edge of a cut not crossed by the current edges builds a minimum spanning tree.

Next: 2.5 Kruskal's algorithm