Lecture 7
Greedy graph algorithms (minimum spanning trees)
CSE 421 Autumn 2026
1
Previously…
2
Greedy algorithms
3
What’s a greedy algorithm?
An algorithm that builds a solution by:
Greedy algorithms
4
Pros
Cons
Simple
Rarely works
When it works, it’s typically very efficient
When it doesn’t work, often gives good approximations
greedily do what appears best for you right here, right now.
Other considerations:
Interval scheduling
5
Greedy algorithm for interval scheduling
Greedy algorithm: Pick the next job to include in the set based on a simple rule.
6
Possible rules?
These were the winners
Some takeaways
7
You’ll probably have a few ideas for “simple rules” for greedy algorithms! Check what happens on some simple examples to rule out some of them.
Proofs of correctness may not be easy: generally, try to find a reason why the greedy algorithm is staying ahead of all other algorithms at every step.
Today
8
Minimum spanning trees
9
An electric company needs to choose where to build wires to connect all the cities below to their plant.
The company knows how much it would cost to lay electric wires between each pair of cities, and wants to find the cheapest way to ensure electricity flows from the plant to every city.
Minimum spanning trees
Input: A connected graph , edge weights
Output: A tree such that every vertex is included and� is minimized. This is called a minimum spanning tree.
10
Minimum spanning forests
Input: A (not necessarily connected) graph , edge weights
Output: consisting of a minimum spanning tree for each connected component. This is called a minimum spanning forest.
11
Greedy MST algorithms
12
Build up the set of edges according to a simple rule.
Never go back and change.
Possible rules?
Prim’s algorithm
Kruskal’s algorithm
Prim’s algorithm
13
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
14
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
15
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
16
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
17
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
18
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
19
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
20
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
21
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
22
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Prim’s algorithm
23
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
24
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
25
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
26
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
27
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
28
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
29
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
30
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
31
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
32
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
Kruskal’s algorithm
33
2
-7
1
6
4
2
3
8
-4
-1
4
3
1
5
A unified argument for proving correctness
Of both Prim’s and Kruskal’s algorithm
34
A unified argument for proving correctness
Of both Prim’s and Kruskal’s algorithm
35
, the subset of non-dotted edges, is compatible with the cut
Proving correctness of greedy MST algorithms
Definition: An edge is safe for some subset of edges if there is some cut compatible with such that is the minimum weight edge crossing the cut.
36
Proving correctness of greedy MST algorithms
Definition: An edge is safe for some subset of edges if there is some cut compatible with such that is the minimum weight edge crossing the cut.
37
Proving correctness of greedy MST algorithms
Definition: An edge is safe for some subset of edges if there is some cut compatible with such that is the minimum weight edge crossing the cut.
38
Proving correctness of greedy MST algorithms
Definition: An edge is safe for some subset of edges if there is some cut compatible with such that is the minimum weight edge crossing the cut.
39
Proving correctness of greedy MST algorithms
Definition: An edge is safe for some subset of edges if there is some cut compatible with such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
40
This theorem is quite powerful! Once we prove it, we’ll just have to show that both Prim and Kruskal select safe edges at each step.
Proving correctness of greedy MST algorithms
Definition: An edge is safe for some subset of edges if there is some cut compatible with such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Proof: Consider a greedy algorithm as above. Denote by the sequence of selected edges. We will show that each is always contained in an MST. In particular, if this is true for , then must be an MST.
41
Proving correctness of greedy MST algorithms
42
Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Proof: Consider a greedy algorithm as above. Denote by the sequence of selected edges. We will show that each is always contained in an MST.
Proving correctness of greedy MST algorithms
43
Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Proof: Consider a greedy algorithm as above. Denote by the sequence of selected edges. We will show that each is always contained in an MST. Suppose not.
Let be the first (safe) edge added by the algorithm such that is contained in an MST , but is not.
Black edges: �Red edges: other edges of the MST containing �Dotted edges: other edges in
Proving correctness of greedy MST algorithms
44
Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Proof: Consider a greedy algorithm as above. Denote by the sequence of selected edges. We will show that each is always contained in an MST. Suppose not.
Let be the first (safe) edge added by the algorithm such that is contained in an MST , but is not. Then, contains exactly one cycle (since we added one edge to a sp. tree).
This cycle must contain some other edge that connects and .
Black edges: �Red edges: other edges of the MST containing �Dotted edges: other edges in
Why?
Final observation: removing from , removes the only cycle, and thus leaves a spanning tree!
Crucially, by our greedy rule, .
The weight of this tree is less than that of , so it’s also an MST! Contradiction.
Proving correctness of greedy MST algorithms
45
Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Now that we have this powerful hammer.. we can use it to prove correctness of Prim’s and Kruskal’s algorithms.
All that we need to do is argue that they always add an edge that is safe for the current edge set.
Proving correctness of greedy MST algorithms
Prim’s algorithm
46
Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Adds the minimum-weight edge from the current tree to the rest.
Is this edge safe for ?
Yes, take to be the vertices spanned by . Then is trivially compatible with . Moreover, by definition, Prim picks to be the minimum-weight edge from to the rest, i.e. from to .
Proving correctness of greedy MST algorithms
Kruskal’s algorithm
47
Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.
Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.
Adds the minimum-weight edge that does not create a cycle.
So, take to be the vertex set of the connected component containing . Then, by construction no edges of cross the cut .
Is this edge safe for the current edge set ?
By definition of Kruskal, does not create a cycle, so and must lie in different connected components of the subgraph .
Moreover, any edge that crosses the cut does not create a cycle in , and is the minimum-weight such edge.
Greedy algorithm proof strategies
48
What we did to prove correctness of greedy algorithm that adds safe edges.