1 of 42

Lecture 7

Greedy graph algorithms (minimum spanning trees)

CSE 421 Autumn 2025

1

2 of 42

Previously…

2

3 of 42

Greedy algorithms

3

What’s a greedy algorithm?

An algorithm that builds a solution by:

  • Considering objects one at a time, using a simple rule to decide on each object
  • Never going back and changing its mind.

In a nutshell: greedily do what appears best for you right here, right now.

4 of 42

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.

  • When designing greedy algorithms, there are often multiple equally intuitive options for what it means to be “greedy”.
  • May not be easy to prove correctness (typically need to find a key structural property of the problem)

Other considerations:

5 of 42

Interval scheduling

  •  

5

6 of 42

Today

6

  • Greedy graph algorithms (minimum spanning tree: Prim’s and Kruskal’s)

7 of 42

Minimum spanning trees

7

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.

8 of 42

Minimum spanning trees

  •  

8

9 of 42

Minimum spanning forests

  •  

9

10 of 42

Greedy MST algorithms

10

Build up the set of edges according to a simple rule.

Never go back and change.

Possible rules?

 

Prim’s algorithm

Kruskal’s algorithm

11 of 42

Prim’s algorithm

  •  

11

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

12 of 42

Prim’s algorithm

  •  

12

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

13 of 42

Prim’s algorithm

  •  

13

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

14 of 42

Prim’s algorithm

  •  

14

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

15 of 42

Prim’s algorithm

  •  

15

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

16 of 42

Prim’s algorithm

  •  

16

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

17 of 42

Prim’s algorithm

  •  

17

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

18 of 42

Prim’s algorithm

  •  

18

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

19 of 42

Prim’s algorithm

  •  

19

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

20 of 42

Prim’s algorithm

  •  

20

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

21 of 42

Prim’s algorithm

  •  

21

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

22 of 42

Kruskal’s algorithm

  •  

22

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

23 of 42

Kruskal’s algorithm

  •  

23

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

24 of 42

Kruskal’s algorithm

  •  

24

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

25 of 42

Kruskal’s algorithm

  •  

25

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

26 of 42

Kruskal’s algorithm

  •  

26

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

27 of 42

Kruskal’s algorithm

  •  

27

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

28 of 42

Kruskal’s algorithm

  •  

28

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

29 of 42

Kruskal’s algorithm

  •  

29

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

30 of 42

Kruskal’s algorithm

  •  

30

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

31 of 42

Kruskal’s algorithm

  •  

31

2

-7

1

6

4

2

3

8

-4

-1

4

3

1

5

32 of 42

A unified argument for proving correctness

Of both Prim’s and Kruskal’s algorithm

  •  

32

 

 

33 of 42

A unified argument for proving correctness

Of both Prim’s and Kruskal’s algorithm

  •  

33

 

 

 

34 of 42

Proving correctness of greedy MST algorithms

  •  

34

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.

35 of 42

Proving correctness of greedy MST algorithms

  •  

35

36 of 42

Proving correctness of greedy MST algorithms

36

 

Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.

 

37 of 42

Proving correctness of greedy MST algorithms

37

 

 

Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.

 

 

 

38 of 42

Proving correctness of greedy MST algorithms

38

 

 

 

Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.

 

 

 

 

Why?

 

 

 

39 of 42

Proving correctness of greedy MST algorithms

39

 

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.

40 of 42

Proving correctness of greedy MST algorithms

Prim’s algorithm

40

 

Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.

 

 

 

41 of 42

Proving correctness of greedy MST algorithms

Kruskal’s algorithm

41

 

Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.

 

 

 

 

 

42 of 42

Greedy algorithm proof strategies

  • “Greedy algorithm stays ahead”: Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithms
  • Structural: Show that the optimal solution must have a certain useful property. And that the greedy algorithm produces a solution with this property.
  • Exchange argument: We can gradually transform any solution into the one found by the greedy algorithm with each transformation only improving or maintaining the value of the current solution.

42

What we did to prove correctness of greedy algorithm that adds safe edges.