1 of 36

Lecture 6

Graph modeling, Greedy algorithms

CSE 421 Autumn 2025

1

2 of 36

Previously…

2

3 of 36

Graph traversal applications

3

BFS

Shortest path (unweighted graphs)

DFS

Strongly connected components

Topological sort

Either one:

Bipartiteness testing (aka 2-coloring)

Connected components

Cycle detection

4 of 36

Takeaways

4

  • When searching through a graph, order matters! BFS and DFS do different things.
  • You can solve several graph problems by just using BFS or DFS with some small modifications: usually just keeping track of some extra information, or calculating something at each vertex, or use edge classification.

5 of 36

Today

5

  • Graph modeling (various examples)
  • Greedy algorithms (intro and “interval scheduling”)

6 of 36

Graph modeling

6

Most of the time, you don’t need a new graph algorithm. What you need to figure out is what graph to make and what graph algorithm to use!

“Graph modeling” is the process of going from a word problem to a graph problem. Often finding a way to turn your requirements into graph features.

This is a mix of “standard bag of tricks” and creativity.

7 of 36

Graph modeling process

7

  1. What are the problem’s main objects?�These will probably (but not always!) become the vertices
  2. How are these objects related?�Usually represent the relationships with edges
  3. How is what I’m looking for encoded in the graph?�Do I need a path from s to t? The shortest path from s to t? A minimum spanning tree? Something else?
  4. Do I know how to find what I’m looking for?�Then run that algorithm/combination of algorithms.�If not, go back to step 1, and try again.�

8 of 36

Example #1

8

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

You made a new social networking app, PurpleGraph. Users on PurpleGraph can have “asymmetric” following (I can follow you, without you following me). You decide to allow people to form multi-user direct messages, but only if people are probably in a similar social circle.

You’ll allow a messaging channel to form only if for every pair of users A,B in the channel: A must follow B or follow someone who follows B or follow someone who follows someone who follows B, or … �And the same for B to A.

You’d like to be able to quickly check if any new proposed channel whether it meets this condition.

9 of 36

Example #1

9

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

Users

Directed - from u to v if �u follows v

If everyone in the proposed channel is in the same SCC

Find SCCs to test a new channel. Make sure all are in the same component

You made a new social networking app, PurpleGraph. Users on PurpleGraph can have “asymmetric” following (I can follow you, without you following me). You decide to allow people to form multi-user direct messages, but only if people are probably in a similar social circle.

You’ll allow a messaging channel to form only if for every pair of users A,B in the channel: A must follow B or follow someone who follows B or follow someone who follows someone who follows B, or … �And the same for B to A.

You’d like to be able to quickly check if any new proposed channel whether it meets this condition.

10 of 36

Example #2

10

Sports fans often use the “transitive law” to predict sports outcomes: in general, if you think A is better than B, and B is also better than C, then you expect that A is better than C.

However, teams don’t all play each other – from data of games that have been played, determine if the “transitive law” is realistic, or misleading about at least one outcome. 

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

11 of 36

Example #2

11

Sports fans often use the “transitive law” to predict sports outcomes: in general, if you think A is better than B, and B is also better than C, then you expect that A is better than C.

However, teams don’t all play each other – from data of games that have been played, determine if the “transitive law” is realistic, or misleading about at least one outcome. 

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

Teams

Directed - from u to v if �u beat v

A cycle would say it’s not realistic. A topological sort would say it is.

Cycle-detection DFS, or topological sort (with error detection)

12 of 36

Example #3

12

You are at Indiana Jones. Your friend is at Space Mountain. You have to tell each other about your experiences in person as soon as possible. Where do you meet and how quickly can you get there?

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

5

3

5

6

3

4

5

4

8

3

5

5

4

6

5

5

4

13 of 36

Example #3

13

You are at Indiana Jones. Your friend is at Space Mountain. You have to tell each other about your experiences in person as soon as possible. Where do you meet and how quickly can you get there?

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

Rides

Walkways weighted by time it takes to walk

The “midpoint”.

  • Dijkstra’s from Indiana Jones. Store distances.
  • Dikstra’s from Space Mtn. Store distances.
  • Iterate over vertices. Find max of two.
  • Iterate over vertices, find min of previous numbers.

5

3

5

6

3

4

5

4

8

3

5

5

4

6

5

5

4

14 of 36

Example #4

14

You are going to a party at a friend’s house. You want to pick up ice-cream along the way. There are several stores. Which path is quickest?

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

The vertices

The edges (weighted)

 

 

A

B

3

7

2

5

4

3

4

3

2

2

3

5

4

3

3

4

3

1

2

15 of 36

Example #4

15

An alternative clever idea for this problem:

 

 

 

 

 

Think of the extra bit as keeping track of whether the ice-cream has been picked up or not

16 of 36

Example #4

16

An alternative clever idea for this problem:

 

 

 

 

 

Think of the extra bit as keeping track of whether the ice-cream has been picked up or not

17 of 36

Example #4

17

You are going to a party at a friend’s house. You want to pick up ice-cream along the way. There are several stores. Which path is quickest?

What are the vertices?

What are the edges?

What are we looking for?

What do we run?

Two copies of the vertices! Now a vertex also stores information about whether ice-cream has been picked up or not!

Two copies of the original ones + edges between each ice-cream store and its copy.

Shortest path from (A, 0) to (B,1)

A

B

3

7

2

5

4

3

4

3

2

2

3

5

4

3

3

4

3

1

2

Dijkstra’s: one run is enough (on a graph that is twice the size)!

18 of 36

Greedy algorithms

18

19 of 36

This week..

19

Another abrupt change of topic.

In fact, the whole course is a sequence of seemingly abrupt changes of topic!

We’re building up a toolkit! A bag of common techniques to approach a variety of algorithmic problems.

Think of each week as a new tool in your toolkit.

20 of 36

Greedy algorithms

20

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.

21 of 36

Greedy algorithms

21

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:

22 of 36

Interval scheduling

  •  

22

Largest number of jobs�(length doesn’t matter)

23 of 36

Interval scheduling

  •  

23

Largest number of jobs�(length doesn’t matter)

24 of 36

Interval scheduling

  •  

24

Largest number of jobs�(length doesn’t matter)

This is the maximal one

25 of 36

Greedy algorithm for interval scheduling

Greedy algorithm: Pick the next job to include in the set based on a simple rule.

25

Possible rules?

  • Earliest start time
  • Latest start time
  • Earliest end time
  • Latest end time
  • Shortest duration

i.e. pick the job with earliest start time, and include it in the set. Then, pick the job with the next earliest start time (that doesn’t overlap), etc.

26 of 36

Greedy algorithm for interval scheduling

Greedy algorithm: Pick the next job to include in the set based on a simple rule.

26

Possible rules?

  • Earliest start time

27 of 36

Greedy algorithm for interval scheduling

Greedy algorithm: Pick the next job to include in the set based on a simple rule.

27

Possible rules?

?

Notice that there is a symmetry:�“Earliest start time” is the same as�“Latest end time” if we look at the jobs from right to left!

  • Earliest start time
  • Latest start time
  • Earliest end time
  • Latest end time
  • Shortest duration

28 of 36

Greedy algorithm for interval scheduling

Greedy algorithm: Pick the next job to include in the set based on a simple rule.

28

Possible rules?

?

  • Earliest start time
  • Latest start time
  • Earliest end time
  • Latest end time
  • Shortest duration

Notice that there is a symmetry:�“Earliest start time” is the same as�“Latest end time” if we look at the jobs from right to left!

29 of 36

Greedy algorithm for interval scheduling

Greedy algorithm: Pick the next job to include in the set based on a simple rule.

29

Possible rules?

  • Shortest duration

30 of 36

Greedy algorithm for interval scheduling

Greedy algorithm: Pick the next job to include in the set based on a simple rule.

30

Possible rules?

  • Earliest start time
  • Latest start time
  • Earliest end time
  • Latest end time
  • Shortest duration

?

?

Again notice that, by symmetry, these�two rules are essentially the same (they don’t necessarily pick the same sets, but one picks an optimal set iff the other does)

31 of 36

Greedy algorithm for interval scheduling

  •  

31

Proof of correctness:

 

32 of 36

Greedy algorithm for interval scheduling

32

 

 

 

33 of 36

Greedy algorithm for interval scheduling

  •  

33

Proof of correctness:

 

 

Now, that we have the claim, let’s complete the proof..

34 of 36

Greedy algorithm for interval scheduling

  •  

34

 

 

35 of 36

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.

35

36 of 36

Summary

36

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.

Greedy algorithms rarely work. But when they work, and you can prove so, they tend to be very efficient (and simple to implement)!

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.