Lecture 4

BFS applications, DFS and applications

CSE 421 Autumn 2025

1

Previously…

2

Graph traversal

Breadth-first search (BFS)

Breadth-first search (BFS)

5

Breadth-first search (BFS)

6

Breadth-first search (BFS)

7

Breadth-first search (BFS)

8

Breadth-first search (BFS)

9

Breadth-first search (BFS)

Breadth-first search (BFS)

10

Breadth-first search (BFS)

11

Breadth-first search (BFS)

12

Breadth-first search (BFS)

13

Breadth-first search (BFS)

14

Breadth-first search (BFS)

15

Breadth-first search (BFS)

16

Breadth-first search (BFS)

17

Breadth-first search (BFS)

18

Breadth-first search (BFS)

19

Today

20

• Applications of BFS (bipartiteness testing)
• DFS and applications (cycle detection, finding strongly connected components, topological sorting)

Old BFS applications

• Find shortest path between two vertices in an unweighted graph:

​

• Run BFS with layers (next slide)

Maximal set of vertices such that there is a path between any two

BFS with layers

• We leverage the fact that BFS naturally considers vertices in order of distance from the source
• Same algorithm as before except we keep track of the “layers”

BFS with layers

• We leverage the fact that BFS naturally considers vertices in order of distance from the source
• Same algorithm as before except we keep track of the “layers”

A new application: Bipartiteness Testing

We’ll adapt BFS to give an algorithm for bipartiteness testing, and prove a graph theory result along the way

A new application: Bipartiteness Testing

Proof:

25

Theorem: A graph is bipartite iff it contains no odd cycles.

We cannot color an odd cycle (let alone the rest of the graph): start from any vertex and give it the color blue; this forces the next vertex to the right to be red, and the next to be blue, and so on.. the last vertex will have the same color as the starting one, due to the odd number.

(“bipartite” implies “no odd cycles”)

A new application: Bipartiteness Testing

Proof:

26

Theorem: A graph is bipartite iff it contains no odd cycles.

Suppose the graph contains no odd cycles.

(“no odd cycles” implies “bipartite”)

Black edges: the ones along which we have walked in our BFS run. But there can be others!

A new application: Bipartiteness Testing

Proof:

27

Theorem: A graph is bipartite iff it contains no odd cycles.

Suppose the graph contains no odd cycles.

No, because this creates an odd cycle!

(“no odd cycles” implies “bipartite”)

A new application: Bipartiteness Testing

Proof:

Theorem: A graph is bipartite iff it contains no odd cycles.

Suppose the graph contains no odd cycles.

No, because this creates an odd cycle!

(“no odd cycles” implies “bipartite”)

Note: we proved a graph theory fact by running an algorithm!

A new application: Bipartiteness Testing

Algorithm for Bipartiteness Testing based on BFS:

Runtime:

A new application: Bipartiteness testing

Algorithm for Bipartiteness testing based on BFS:

Note: If the graph has multiple connected components one just needs to run the above algorithm for each component (and either combine all the colorings, or output “not bipartite” if any of the components is not bipartite)

Depth-first search

• Breadth-first search visits all the neighbors before diving in deeper
• Depth-first search visits as deep as possible
• They are essentially the same algorithm, but with a different data structure!����

31

BFS: Queue — first in, first out���DFS: Stack — first in, last out

Breadth-first search (BFS)

32

Depth-first search (DFS)

“Stack” version

33

Depth-first search (DFS)

“Stack” version

34

Order of vertices popping off the stack:

(assuming we loop from right to left):

Depth-first search (DFS)

“Recursive” version

35

(assuming we loop from left to right):

Same processing order as before

More applications of graph traversal

- undirected graphs

36

• Finding spanning trees
• Detecting cycles

Spanning trees

37

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

38

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

39

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

40

All descendants of a given vertex

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

41

Def. A cross edge is an edge that connects a vertex to a vertex in another “branch”

All descendants of a given vertex

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

42

Def. A cross edge is an edge that connects a vertex to a vertex in another “branch”

All descendants of a given vertex

Similarly, this is also a cross edge, and is not present in the graph

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

43

Def. A back edge is an edge that connects a vertex to an ancestor that is not it’s parent in the tree.

Yes it can exist!

Is there any other type of edge (other than cross and back edges)?

No, that’s all!

Q1: does a graph with a back edge contain a cycle?

Q2: does a graph with a cycle contain a back edge?

Yes!

Yes!

Understanding the DFS spanning tree

What do the edges not included in the spanning tree look like?

44

Def. A back edge is an edge that connects a vertex to an ancestor that is not it’s parent in the tree.

Is there any other type of edge (other than cross and back edges)?

No, that’s all!

Useful Fact: A graph contains a cycle iff it has a back edge.

This suggests the following algorithm to decide if a graph has a cycle:

• Run DFS and check if you ever encounter a back edge

Can also use DFS for bipartiteness testing:

• Run DFS and check if you ever encounter a back edge that forms an odd cycle (connects to an ancestor two steps away)

Equivalently, color each vertex alternately red and blue and check if a back edge ever connects to same-color vertices

Recall: a graph is bipartite iff it contains an odd cycle