Depth First Search
Depth-first search (DFS) follows the strategy to search ”deeper” in the graph whenever possible. In DFS, edges are recursively explored out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the search ”backtracks” to explore edges leaving the vertex from which v was discovered.
This process continues until all the vertices that are reachable from the original source vertex have been discovered. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source.
DFS timestamps each vertex as follows:
d[v] records when v is first discovered.
f[v] records when the search finishes examining v’s adjacency list.
Write a program which reads a directed graph G=(V,E) and demonstrates DFS on the graph based on the following rules:
G is given in an adjacency-list. Vertices are identified by IDs 1,2,...n respectively.
IDs in the adjacency list are arranged in ascending order.
The program should report the discover time and the finish time for each vertex.
When there are several candidates to visit during DFS, the algorithm should select the vertex with the smallest ID.
The timestamp starts with 1.