Dashboard/Block 4: Flows & Algorithms/Week 13
Week 13Flows & Algorithms

DFS & Topological Ordering

We conclude with Depth-First Search (DFS) and its applications. DFS discovers the structure of a graph: back edges reveal cycles, DFS timestamps enable topological ordering of DAGs, and DFS forests reveal connected components.

Learning Objectives

Implement and trace DFS with discovery/finish times
Classify edges as tree, back, forward, or cross edges
Compute topological ordering of a DAG using DFS
Detect cycles using DFS

Key Concepts

Depth-First Search

DFS explores a graph by going as deep as possible before backtracking. It assigns discovery time d[v]d[v] and finish time f[v]f[v] to each vertex, which encode the structure of the search.

Edge classification in directed graphs:

  • -Tree edge: discovers a new vertex
  • -Back edge: goes to an ancestor → indicates a cycle
  • -Forward edge: goes to a descendant (non-tree)
  • -Cross edge: goes to a vertex in a different subtree
  • -

    DFS runs in O(n+m)O(n + m) time

  • -

    A directed graph has a cycle iff DFS finds a back edge

  • -

    In undirected graphs, only tree and back edges exist

  • -

    Parenthesis property: [d[u],f[u]][d[u], f[u]] and [d[v],f[v]][d[v], f[v]] are either nested or disjoint

Topological Ordering

A topological ordering of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every edge (u,v)(u, v), uu comes before vv.

DFS gives a topological order: sort vertices by decreasing finish time f[v]f[v].

  • -

    A DAG always has a topological ordering

  • -

    DFS finish times in reverse order give a topological ordering

  • -

    A directed graph is a DAG iff it has no back edges in DFS

  • -

    Applications: scheduling, dependency resolution, course prerequisites

W12: Dijkstra & Bellman-Ford