Course contentsShow
← Computer Science
Lesson 715 of 2,87217. Graph Traversal AlgorithmsFree lesson

DFS Discovery and Finish Times

Track discovery and finish times during DFS for ordering and classification purposes.

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:

  1. Increment the counter and record it as discovery[v]
  2. Recursively explore all neighbors
  3. 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.