1 of 54

Lecture 5

DFS applications, Graph modeling

CSE 421 Autumn 2026

1

2 of 54

Previously…

2

3 of 54

BFS and DFS

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

3

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

4 of 54

BFS and DFS

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

4

Applications of BFS from previously:

  • Finding connected components
  • Finding shortest path in an unweighted graph (BFS with layers)
  • Bipartiteness testing

5 of 54

Depth-first search (DFS)

“Recursive” version

5

DFS():

    • Set to visited.
    • For each neighbor of :
      • If is not visited:

DFS()

Order of completion:

6 of 54

Spanning trees

  • A spanning tree for a graph is a subgraph of that is a tree (i.e. contains no cycles), and touches every vertex.
  • Any graph traversal algorithm generates a spanning tree (if we “draw” the edges of our walk). This is because we never visit the same vertex twice.
  • So, BFS and DFS both “generate” spanning trees but they are different!

6

7 of 54

Understanding the DFS spanning tree

(this is helpful for designing other algorithms based on DFS)

7

Let this be a spanning tree obtained via DFS. These are the edges we walked along.

8 of 54

Understanding the DFS spanning tree

(this is helpful for designing other algorithms based on DFS)

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

8

Let this be a spanning tree obtained via DFS. These are the edges we walked along.

9 of 54

Understanding the DFS spanning tree

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

9

(this is helpful for designing other algorithms based on DFS)

Let this be a spanning tree obtained via DFS. These are the edges we walked along.

10 of 54

Understanding the DFS spanning tree

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

10

All descendants of a given vertex

(this is helpful for designing other algorithms based on DFS)

Let this be a spanning tree obtained via DFS. These are the edges we walked along.

11 of 54

Understanding the DFS spanning tree

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

11

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

All descendants of a given vertex

(this is helpful for designing other algorithms based on DFS)

(Two vertices are in different branches if they are not “descendant” of one another)

12 of 54

Understanding the DFS spanning tree

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

12

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

(this is helpful for designing other algorithms based on DFS)

13 of 54

Understanding the DFS spanning tree

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

13

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!

(this is helpful for designing other algorithms based on DFS)

(Because a tree has no cycles by definition, and back edges are the only other edges in the graph, as we have argued)

14 of 54

Understanding the DFS spanning tree

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

14

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 an even number of 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

(this is helpful for designing other algorithms based on DFS)

15 of 54

Today

15

  • DFS and applications in directed graphs (finding strongly connected components, topological sorting)

16 of 54

Directed graphs

16

17 of 54

Depth-first search on directed graphs

  • Same as DFS on undirected graphs except, if we are at , we only add neighbor if an edge points from .
  • DFS starting from will visit all vertices reachable by a directed path .

17

18 of 54

Depth-first search on directed graphs

  • Same as DFS on undirected graphs except, if we are at , we only add neighbor if an edge points from .
  • DFS starting from will visit all vertices reachable by a directed path .

18

19 of 54

Depth-first search on directed graphs

  • Same as DFS on undirected graphs except, if we are at , we only add neighbor if an edge points from .
  • DFS starting from will visit all vertices reachable by a directed path .

19

20 of 54

Depth-first search on directed graphs

  • Same as DFS on undirected graphs except, if we are at , we only add neighbor if an edge points from .
  • DFS starting from will visit all vertices reachable by a directed path .

20

21 of 54

DFS edge nomenclature (directed graphs)

21

22 of 54

DFS edge nomenclature (directed graphs)

22

Back edge�Connects vertex to its ancestor in DFS tree

23 of 54

DFS edge nomenclature (directed graphs)

23

Back edge�Connects vertex to its ancestor in DFS tree. Can exist.

24 of 54

DFS edge nomenclature (directed graphs)

24

Forward edge�Connects vertex to its descendant in DFS tree.

Back edge�Connects vertex to its ancestor in DFS tree. Can exist.

25 of 54

DFS edge nomenclature (directed graphs)

25

Forward edge�Connects vertex to its descendant in DFS tree.�Can exist.

Back edge�Connects vertex to its ancestor in DFS tree. Can exist.

26 of 54

DFS edge nomenclature (directed graphs)

26

Cross edge�Connects vertices across branches.

Back edge�Connects vertex to its ancestor in DFS tree. Can exist.

Forward edge�Connects vertex to its descendant in DFS tree.�Can exist.

27 of 54

DFS edge nomenclature (directed graphs)

27

Cross edge�Connects vertices across branches. Can only exist if high -> low.

Back edge�Connects vertex to its ancestor in DFS tree. Can exist.

Forward edge�Connects vertex to its descendant in DFS tree.�Can exist.

28 of 54

DFS edge nomenclature (directed graphs)

28

Tree edge�The edges in the DFS tree

Never-considered edge�The edges that are not even �considered during DFS

Q: How do we use this information to decide if a graph has a directed cycle?

Back edge�Connects vertex to its ancestor in DFS tree. Can exist.

Forward edge�Connects vertex to its descendant in DFS tree.�Can exist.

Cross edge�Connects vertices across branches. Can only exist if high -> low.

Same as for undirected graphs: a cycle exists iff there is back edge!

So run DFS and check if you encounter a back edge.

29 of 54

Finding strongly connected components (SCC)

  • Vertices and are strongly connected iff they are on a “directed cycle”, i.e. there is a directed path and a directed path .
  • Every directed graph’s vertices can be partitioned into strongly connected components where all pairs of vertices in the component are strongly connected
  • SCCs can be found by extending DFS algorithm in time
  • See wikipedia or other sources for details! (You can assume such an algorithm in your HWs - as all other 332 algorithms).

29

30 of 54

Finding strongly connected components (SCC)

30

31 of 54

Shrinking a directed graph to a DAG

31

32 of 54

Directed acyclic graphs

  • A directed graph is acyclic iff it has no directed cycles
  • Also referred to as a DAG
  • If we shrink every strongly connected component to a vertex, this converts the directed graph into a DAG

32

33 of 54

Shrinking a directed graph to a DAG

33

34 of 54

Topological sorting

34

Input: A DAG

Output: A numbering of vertices such that all edges go from lower to higher.

35 of 54

Topological sorting

DFS():

  • Mark as visited.
  • For each neighbor of :

If is not visited:

DFS()

  • Add to stack

35

Input: A DAG

Output: A numbering of vertices such that all edges go from lower to higher.

Topo-sort():

  • Initialize an empty stack.
  • For each vertex :
    • If is not visited:
      • Run DFS()
  • Return elements of stack.

Small but key modification

Note that this returns them in reverse order of when they are added.

36 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

37 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

38 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

39 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

40 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

41 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

42 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

43 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

44 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

45 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

46 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

47 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

5

48 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

5

4

49 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

5

4

3

Run DFS

Run DFS

50 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

5

4

3

Run DFS

Run DFS

2

51 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

5

4

3

Run DFS

Run DFS

2

1

Why this works: if vertex terminates before vertex , then cannot be an ancestor of :

  • Either is a descendant of , or
  • They are on distinct branches, and ’s branch happened to be processed first.

52 of 54

Topological sorting walkthrough

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

Run DFS

15

14

13

12

Run DFS

Run DFS

11

10

9

8

Run DFS

Run DFS

Run DFS

Run DFS

7

6

5

4

3

Run DFS

Run DFS

2

1

Remark: here, we ran the algorithm on a DAG to find a topological sort. One can also run the algorithm on an arbitrary directed graph to decide whether the graph is a DAG (and in that case output a topological sort) or not. One just needs a small modification:

  • If you ever loop over a vertex that already has an outstanding DFS running, output “not a DAG”. Otherwise, output the numbering obtained.

(Convince yourself that this works!)

53 of 54

Summary - graph traversal applications

53

BFS

Shortest path (unweighted graphs)

DFS

Strongly connected components

Topological sort

Either one:

Bipartiteness testing (aka 2-coloring)

Connected components

Cycle detection

54 of 54

Takeaways

54

  • 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.