In the Depth-First Search (DFS) algorithm, the concepts of discovery
time and finishing time are used to track the sequence of events as nodes
are visited in a graph. These times are essential in understanding the order
in which nodes are explored and processed during the DFS traversal.
Discovery Time
Definition: The discovery time of a node is the timestamp recorded
when the DFS first visits the node.
Significance: It indicates when the exploration of a node begins. At
this moment, the node is marked as "visited," but its neighbors might
not yet have been explored.
Finishing Time
Definition: The finishing time of a node is the timestamp recorded
when DFS has finished exploring all the neighbors of the node, and the
recursive call for that node ends.
Significance: It represents the completion of exploration for the node
and its adjacent nodes.
Role of Recursion in DFS
DFS is naturally recursive, and recursion plays a key role in:
1. Implicit Stack Management:
o Recursion handles the backtracking automatically by using the
function call stack.
o When DFS visits a node, it recursively explores all its neighbors.
If a neighbor has not been visited, the recursive call moves
deeper into the graph.
2. Traversal Logic:
o For each node, DFS recursively visits its unvisited neighbors until it reaches a
node with no unvisited neighbors.
o Once all neighbors are processed, the recursion unwinds, moving back up the call
stack.
3. Recording Discovery and Finishing Times:
o Discovery time is recorded when a node is visited (when the recursive function
for that node is called).
o Finishing time is recorded when the recursive function for that node returns after
exploring all its neighbors.
Uses of Discovery and Finishing Times
Cycle Detection: Identifying back edges in directed graphs.
Topological Sorting: In a Directed Acyclic Graph (DAG), the order of
finishing times determines the topological order.
Strongly Connected Components: Used in algorithms like Kosaraju's and
Tarjan's to identify SCCs.
Edge Classification: Classify edges as tree, back, forward, or cross edges
based on discovery and finishing times.
Example:
Graph Representation
Vertices: {A,B,C,D,E}
Edges:
{(A,B),(A,C),(B,D),(C,E),(D,E)}
Adjacency List
A:{B,C}
B:{D}
C:{E}
D:{E}
E:{}
DFS Execution
We start at vertex A, assign discovery times when a node is first
visited, and assign finishing times when all its neighbors have been
fully explored.
DFS Process
Step 1: Initialize
Time counter: time=0
Discovery and finishing times: discovery[v]=−1, finish[v]=−1 for all
v∈{A,B,C,D,E} in v∈{A,B,C,D,E}.
Step 2: Traverse
1. Start at A:
o Discovery time of A=1 (time=1).
o Explore its neighbors: B first, then C
Move to B
Discovery time of B=2 (time=2).
Explore B's neighbor D.
Move to D:
Discovery time of D=3 (time=3).
Explore D's neighbor E.
Move to E:
Discovery time of E=4 (time=4).
E has no unvisited neighbors.
Finishing time of E=5 (time=5).
Backtrack to D:
All neighbors of D are explored.
Finishing time of D=6 (time=6).
Backtrack to BBB:
All neighbors of B are explored.
Finishing time of B=7 (time=7).
Backtrack to A and explore C:
Discovery time of C=8 (time=8).
Explore C's neighbor E, but E is already visited.
Backtrack to C:
All neighbors of C are explored.
Finishing time of C=9 (time=9).
Backtrack to A:
All neighbors of A are explored.
Finishing time of A=10 (time=10).
DFS Tree Representation
A→B→D→E
A→C→E (but E was already visited).
This order demonstrates the recursive nature of DFS and the
discovery/finishing sequence.
