Depth-first search (DFS) is a general technique for traversing a graph
A DFS traversal of a graph G.
Visits all the vertices and edges of G n Determines whether G is connected.
Computes the connected components of G.
Computes a spanning forest of G
DFS on a graph with n vertices and m edges takes O(n + m ) time
q DFS can be further extended to solve other graph problems
n Find and report a path between two given vertices
n Find a cycle in the graph
q Depth-first search is to graphs what Euler tour is to binary trees
Properties of DFS
DFS(G, v) visits all the vertices and edges in the connected component of v
The discovery edges labeled by DFS(G, v) form a spanning tree of the connected component of v
Applications of DFS :
DFS traversal of a graph G can be used to solve the following problems in O(V + E) time (using a stack S) by keeping track of path from start node v to current vertex
Find path from vertex v to u by invoking DF S(G, v) and keeping track of path until u is reached
Detecting cycle by invoking DF S(G, v) for any v and keeping track of path until a BACK edge is found
DFS is the classic strategy for exploring a maze.
Written with ♥ from Mangesh.