Depth First Search (DFS) is graph traversal algorithm. Using this algorithm, given a source vertex (s), we can answer queries such as
- What are the all the vertices connected to s?
- Is there any path from s to v?
- What is the path from s to v?
For example consider the following undirected graph.
0 is connected to 7 via the path 0 – 2 – 7. But 0 is not connected to 4 or 5 or 6.
The DFS algorithm works by starting at the source vertex, and start exploring the un-visited vertices adjacent to the source vertex. For each of the un-visited vertices, this procedure is recursively applied. So this procedure inherently uses the stack data structure.
We maintain a marked[] array to keep track of the visited vertices. To check if a vertex ‘v’ is reachable from ‘s’, we just need to examine marked[v]. If it true, ‘v’ is connected to ‘s’. Otherwise they not connected.
We also create edgeTo attribute for each vertex which indicates from which vertex, this is being explored. Using this attribute, we can trace the path from a vertex to the source.
We maintain a marked[] array to keep track of the visited vertices. To check if a vertex ‘v’ is reachable from ‘s’, we just need to examine marked[v]. If it true, ‘v’ is connected to ‘s’. Otherwise they not connected.
We also create edgeTo attribute for each vertex which indicates from which vertex, this is being explored. Using this attribute, we can trace the path from a vertex to the source.
In the implementation of this algorithm, we use the adjacency list representation of the graph.