DFS Discovery and Finish Times
What you'll learn: How to track when vertices are first visited and fully explored during DFS to understand vertex ordering and relationships.
When running DFS, we can assign two timestamps to each vertex: a discovery time (when we first visit it) and a finish time (when we've fully explored it and all its descendants). Think of it like entering and exiting a building—you note when you arrive and when you leave after checking every room.
Why Track These Times?
Discovery and finish times reveal important structural properties about the graph. They help us:
- Order vertices by when they were discovered or completed
- Classify edges (tree, forward, back, cross edges—which we've already covered)
- Detect relationships between vertices (is one an ancestor of another?)
- Solve advanced problems like topological sorting and finding strongly connected components
How It Works
Maintain a global counter starting at 0. When you first visit a vertex v:
- Increment the counter and record it as
discovery[v] - Recursively explore all neighbors
- Increment the counter again and record it as
finish[v]
The Parenthesis Theorem
Discovery and finish times follow a "nested intervals" pattern. For any two vertices u and v, either:
- Their time intervals are completely disjoint (neither is an ancestor of the other)
- One interval completely contains the other (one is an ancestor)
This is like parentheses: ( u ( v ) ) is valid, but ( u ( v ) ) overlapping isn't possible.
Key Takeaway: Discovery and finish times timestamp when DFS enters and exits each vertex, creating a hierarchical ordering that reveals ancestor-descendant relationships and enables advanced graph algorithms.