Skip to main content

DFS and the Edge Taxonomy

What This Concept Is​

Recursive DFS finishes exploring each child's descendants before advancing to the next outgoing edge. Discovery and finish events define nested or disjoint time intervals. To reproduce this iteratively, keep a stack frame containing the vertex and its next-neighbor iterator; a plain stack of vertices marked at push time is not automatically equivalent for finish times or edge classification.

For directed DFS, a white endpoint creates a tree edge, a gray endpoint gives a back edge, and an already black endpoint is forward or cross according to ancestry. A self-loop is a back edge.

Why It Matters Here​

Finish order supports SCC decomposition and DFS topological ordering. Conflating discovery order with finish order can produce convincing but incorrect component partitions. Explicit frames also avoid interpreter recursion limits on long chains.

Concrete Examples​

Process adjacency in order for edges 0→1,1→2,2→1,0→2 and roots in increasing order. Discover 0,1,2; edge 2→1 targets gray 1 and proves a cycle. Finish 2 then 1; later 0→2 is a forward edge to a finished descendant. A separate root's edge to that completed subtree can be a cross edge. Parenthesis intervals nest along tree ancestry and are disjoint for distinct completed subtrees.

For undirected traversal, skip the reverse incidence of the exact tree-edge ID, not every edge to the parent vertex. A second parallel parent edge can be a real two-edge cycle in the multigraph model.

Common Confusion / Misconceptions​

A black endpoint alone does not distinguish forward from cross edges. An undirected tree edge appears twice in adjacency storage but is one physical edge. Changing BFS's queue to a stack gives a reachability procedure, not the full DFS event semantics needed by these proofs.

How To Use It​

Write the event sequence: discover, examine edge, return from child, finish. Use a three-color state for directed cycle detection. For a topological order, reject any directed back edge before reversing finish order. In Lab A, the first Kosaraju pass uses iterator frames and the second only needs reachability.

Check Yourself​

  1. What state must an iterative frame retain?
  2. Why does a gray endpoint prove a directed cycle?
  3. Why must undirected parent handling use edge identity?
  4. Which event order does Kosaraju need?

Mini Drill or Application​

Trace timestamps on the example and an isolated vertex. Implement the frame version on a chain of 2,500 vertices. Compare its finish order to recursive DFS on small safe inputs, then explain why matching reachability alone is too weak a test. See P6.

Read This Only If Stuck​

Find DFS events, edge classification, and iterative stack frames in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.