Searching and Sorting Graphs

Overview

Kent Quanrud develops graph-search techniques from topological sorting through depth-first search (DFS) to strongly connected components (SCCs). He shows how DFS finishing order yields a second linear-time topological sort for directed acyclic graphs, then derives the two-pass Kosaraju algorithm, which finds every SCC in O(n + m) time by searching the reversed graph first and the original graph next.

Key takeaways

For a DAG, repeatedly removing zero-indegree sources computes a topological order in O(n + m) time when indegrees and newly available sources are maintained incrementally.
DFS requires visited marks because recursion alone does not shrink a graph containing cycles; with marks, each vertex and edge is processed at most once.
In a DAG, DFS postorder is reverse topological order: reversing the list gives a topological ordering in O(n + m) time.
A vertex’s SCC is the intersection of vertices reachable from it in the original graph and vertices reachable from it in the reversed graph.
Kosaraju’s algorithm finds all SCCs in O(n + m) time by computing DFS postorder in the reversed graph, then searching the original graph in decreasing finishing-time order.
Contracting SCCs always yields a DAG, because any cycle among contracted components would make those components mutually reachable and therefore part of one SCC.

Chapters

0:00 Graph Basics: Vertices, Edges, and Representations

The lecture uses n for the number of vertices and m for the number of edges.
Directed edges have an orientation; undirected edges represent mutual connections.
Adjacency lists store each vertex’s outgoing neighbors, while adjacency matrices use an n × n table.

1:36 DAGs, Circuit Evaluation, and Topological Order

A directed acyclic graph (DAG) has no directed cycle; vertices with no incoming edges are sources, and vertices with no outgoing edges are sinks.
Boolean circuits form DAGs: inputs flow through gates such as AND, OR, and NOT toward outputs.
A topological ordering puts each vertex before the vertices it points to, allowing circuit gates to be evaluated in order.

6:50 Topological Sorting by Repeatedly Removing Sources

Every nonempty DAG has a source: following incoming edges indefinitely would repeat a vertex and create a cycle.
Repeatedly output and remove a source; update the indegrees of its neighbors and add any newly zero-indegree vertices to a queue.
With indegrees maintained as bookkeeping, source removal computes a topological ordering in O(n + m) time.

10:00 The Cat Maze as a Graph-Reachability Problem

The maze asks whether a path connects the starting cat to the goal while alternating between cats facing toward and away from the viewer.
Modeling locations and permitted moves as vertices and directed edges turns the puzzle into a reachability question.
A second example asks whether a directed graph’s start vertex S can reach every other vertex; a cycle with no incoming edge demonstrates why the answer can be no.

16:57 Why Naive Recursive Reachability Can Loop Forever

A natural recursive procedure tests each outgoing neighbor V to see whether it can reach the target T.
On a cycle, recursive calls can revisit the same vertices indefinitely because the graph does not shrink between calls.
The missing ingredient is memory of visited vertices, which prevents repeated work and breaks recursive cycles.

23:40 DFS Marks Vertices to Search Without Repeating Work

DFS marks a vertex when first visited, explores its neighbors, and returns immediately if it encounters a marked vertex.
The marks act like breadcrumbs in a maze, preventing the search from cycling forever.
Each vertex is marked once and each outgoing edge is examined at most once, so a search takes O(n + m) time.

29:40 Proving DFS Reaches Every Vertex It Can Reach

Assume a vertex W is reachable from the DFS start but remains unmarked; a path from the start to W must cross from marked vertices to unmarked ones.
At that crossing, DFS has marked a vertex A with an edge to an unmarked vertex B.
DFS examines A’s outgoing edges, so it must visit B—a contradiction that proves all reachable vertices are marked.

35:24 DFS Finishing Times Order Reachable Vertices

DFS finishes a vertex only after its recursive exploration of reachable unmarked vertices returns.
If V can reach W but W cannot reach V, any DFS that visits both finishes W before V.
The claim follows by considering whether DFS marks V or W first: either W is explored inside V’s call, or W’s search cannot reach V.

40:26 Topological Sorting by Reversing DFS Postorder

A DFS driver calls DFS from every still-unmarked vertex so disconnected portions of the graph are included.
Appending each vertex when its DFS call finishes produces postorder; in a DAG, this is reverse topological order.
Reversing the postorder list gives another O(n + m) topological sort, using visited marks and finishing order.

44:49 Strong Connectivity and Component Equivalence Classes

Two vertices are strongly connected when each can reach the other; mutual reachability is transitive and therefore partitions vertices into equivalence classes.
Each class is a strongly connected component (SCC), so vertices in one SCC have identical pairwise reachability relationships to vertices outside it.
Contracting each SCC into one vertex produces a DAG: a cycle among contracted components would mean they belong to one larger SCC.

48:52 Finding One SCC with a Reversed-Edge Graph

A forward DFS from vertex V finds all vertices reachable from V; a DFS from V in the reversed graph finds all vertices that can reach V in the original graph.
The intersection of those two reachable sets is exactly V’s SCC.
Building the reversed adjacency lists and running both searches takes O(n + m) time, unlike checking reachability separately from every vertex.

56:04 Why Repeated SCC Searches Need a Better Processing Order

Running the one-component procedure repeatedly can still revisit large parts of the graph and take quadratic time.
If an SCC is a sink in the condensation DAG, a forward DFS from any vertex in it cannot leave the component.
Removing sink components one at a time would avoid redundant searches, so the challenge is to identify a sink SCC efficiently.

1:03:32 DFS Finishing Order Identifies Sink Components

The DFS finishing-time relation orders vertices across SCCs: if one component can reach another, its vertices finish later when DFS searches the original graph.
Running DFS on the reversed graph makes original-graph sink components appear at the end of the postorder list.
After removing a sink component, the same ordering principle applies to the remaining graph, allowing the process to continue.

1:08:30 Kosaraju’s Two-Pass Algorithm Finds All SCCs

First run DFS on the reversed graph and record vertices in postorder.
Process the list from last to first, running DFS in the original graph from each still-unassigned vertex; each search returns one SCC.
Mark or remove each discovered component so every vertex and edge is processed only a constant number of times, yielding O(n + m) total time.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.