C program for Depth First Search(DFS).

Posted by Mangesh on September 03, 2019

Description :

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.

Related Post
1 C program for Depth First Search(DFS).
2 C program for Breadth First Search.
Latest Post
1 shubhanshu
2 test
3 C program for Breadth First Search.
4 C program for Depth First Search(DFS).
5 C for circular queue using linked list.