Traverse graphs and order dependencies

Prerequisites: Adjacency lists, queues, stacks, and directed graphs.

Learning objectives

• Trace BFS distances and parent pointers.
• Use DFS colors to detect directed cycles.
• Construct and validate a topological order.

Distances require a discovery discipline

Represent a directed graph by adjacency lists. Breadth-first search maintains a FIFO frontier, distances, and parent pointers. Mark a vertex discovered when it enters the queue, not when it later leaves, so several incoming edges do not enqueue it repeatedly. When exploring an edge u→v to an undiscovered vertex, set distance[v]=distance[u]+1 and parent[v]=u. Queue order ensures that vertices are processed in nondecreasing distance from the start.

For edges A→B, A→C, B→D, C→D, D→E, start from A. After removing A, the queue is [B,C] with both distances 1. Removing B discovers D at distance 2. Removing C sees D already discovered and leaves its parent unchanged. Removing D discovers E at distance 3. Both A-B-D-E and A-C-D-E are shortest paths; the adjacency order selects which one the parent map reconstructs.

DFS records active obligations

Depth-first search explores a child before returning to the current vertex. In a directed graph, distinguish white vertices not yet discovered, gray vertices whose recursive exploration is active, and black vertices whose outgoing edges are finished. An edge to a gray vertex closes a directed cycle along the active call path. An edge to a black vertex alone does not prove a cycle.

A topological order places every prerequisite before each dependent. For an acyclic graph, reversing DFS finishing order gives one such ordering. Alternatively, Kahn’s algorithm begins with all zero-indegree vertices, repeatedly removes one, and decreases its neighbors’ indegrees. If fewer than all vertices are removed, a directed cycle prevents a complete ordering. A disconnected graph requires starting from every unvisited component, not just one convenient root.

Trace a schedule, then test its certificate

Suppose compile depends on parse, test depends on compile, and package depends on compile and test. The edges are parse→compile, compile→test, compile→package, test→package. Only parse initially has indegree zero. Repeated removal yields parse,compile,test,package. Adding package→parse creates a cycle, and there is no valid prerequisite-first schedule.

A proposed topological order is easy to check: map each vertex to its position and verify position[u]<position[v] for every directed edge. This separates constructing a result from checking its validity. Both BFS and DFS take O(V+E) time on adjacency lists when each vertex and edge is processed a bounded number of times. An adjacency matrix can instead force O(V²) scanning.

Use MIT’s graph lectures to connect the invariant to the proof. When implementing, also specify handling for missing vertices, parallel edges, self-loops, and unreachable targets. Those details determine whether a mathematical graph description and a program’s input format actually agree.

Practice problem

Consider vertices A,B,C,D,E,F and edges A→C, B→C, C→D, C→E, E→F. Trace Kahn’s algorithm, choosing alphabetically among available zero-indegree vertices. Then add F→C and explain which vertices can still be removed before the algorithm detects incomplete progress. Give a valid BFS distance map from A in the original graph.

Worked solution

Initially A and B have indegree zero. Alphabetical choices remove A then B; C becomes available only after both incoming prerequisites are removed. Then remove C, D, E, F, producing A,B,C,D,E,F. With F→C added, A and B can still be removed, but C retains an incoming edge from F, E depends on C, and F depends on E. The remaining cycle blocks C,D,E,F, although D itself is not on the cycle. BFS from A reaches A:0, C:1, D:2, E:2, F:3; B is unreachable and should remain absent or explicitly infinite.

Check your understanding

During directed DFS, u has an edge to v. Which observation directly establishes a directed cycle through the active search path?

• v has a smaller numerical identifier.
• v is black, having completed in an earlier branch.
• v was reached before u by any traversal.
• v is gray, meaning it is still on the active recursion path.

Explanation

An edge to an active ancestor closes a directed path into a cycle. An edge to a completed vertex need not do so.

Kahn’s algorithm removes A and B but leaves C,D,E,F. Edges include C→D,C→E,E→F,F→C. Which conclusion is correct?

• All four remaining vertices lie on a directed cycle.
• C,E,F form a cycle; D can remain blocked without lying on it.
• D must be removed first because it has no outgoing edge.
• The graph is acyclic because two vertices were removed.

Explanation

Kahn removes zero-indegree vertices. D still has incoming C and is blocked downstream of the cycle, though it is not itself cyclic.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →