Depth First Search :
Depth first works by selection one vertex V of G as a start vertex; V is marked visited. Then each
unvisited vertex adjacent to V is serached in trun using depth first serach recursively.This process
continues until a dead end (i.e)a vertex with no adjacent unvisited vertices is encountered.At a deadend the algorithm backsup
one edge to the vertex it came from and tries to continue visiting unvisited vertices from there.
1.To check whether the undirected graph is connected or not.
2.To check whether the connected undirection graph is biconnected or not.]
3.To check the a Acyclicity of the directed graph.
Step 1: Choose any node in the graph . Designate it as the search node and mark it as vivited.
C Program To Implement Graph Traverses Using Depth First Search
Step 2: Using the adjacency matrix of the graph, find a node adjacent to the search node that has not been visited yet. Designate this as the new search node and mark it as visited.
Step 3: Repeat step 2 using t he new search node. If no nodes satisfying(2) can be found, return to the previous search node and continue from there.
Step 4: When a return to the previous search in(3) is impossible,the serach from the originally choosen search node is complete.
Step 5: If the graph still contains unvisited nodes,choose any node that has not been visited and repeat step(1) through(4).
CPP Program To Implement Graph Traverses Using Depth First Search