Depth first traversal or Depth first Search is a recursive algorithm for searching all the vertices of a graph or tree data structure.
In DFS the vertices have three adjacent different statuses during the process of traversal or searching, the status being : unknown, discovered and visited. Initially all the vertices have their status termed as "unknown", after being explored the status of the vertex is changed to "discovered " and after all vertices adjacent to a given vertex are discovered its status is termed as "visited ".
EXAMPLE
Use DFS to visit various vertices for the graph given below. The vertex D is taken as the starting vertex and, if there are more than one vertices adjacent to a vertex, then the adjacent vertices are visited in lexicographic order.
Figure 1 : Status of D changes to discovered.
Figure 2 : D has two neighbors, by convention A is visited first i.e., the status of A changes to discovered.
Figure 3 : A has two unknown neighbors B and C, so status of B changes to discovered.
Figure 4 : Similarly vertex E is discovered.
Figure 5 : All of E’s neighbors are discovered so status of vertex E is changed to visited.
Figure 6 : The nearest unknown neighbor ok B is F, so we change status of F to discovered
Figure 7 : Vertex G is discovered.
Figure 8 : G has two unknown neighbors C and H, so status of C changes to discovered.
Figure 9 : Vertice H is discovered.
Figure 10 : All of H’s neighbors are discovered so status of vertex H is changed to visited.
#include<stdio.h> #include<stdlib.h> //Global Function Declaration void DFS(); // Global Variable Declaration int number_of_vertices, number_of_edges, discover_top=1, visited_top=1, v, i, j, k; int edges[25][2], discovered[25], visited[25]; // main( ) function begins void main() { // Input number of vertices present in the graph printf("\n Enter number of vertices : "); scanf("%d",&number_of_vertices); // Input number of edges present in the graph printf("\n Enter number of edges : "); scanf("%d",&number_of_edges); for(i=0; i<number_of_edges; i++) { printf("Enter an edge (u,v)..."); scanf("%d%d",&edges[i][0],&edges[i][1]); } // Input the vertex from where searching process is start printf("\n Enter the start vertex..."); scanf("%d",&v); DFS(); printf("\n\n\n Final Visited List :\n"); for(i=0; i<=visited_top; i++) printf("\t%d",visited[i]); } // DFS( ) function begins void DFS() { int temp[25]; int pos,z; discover_top++; discovered[discover_top]=v; for(z=1; z<=number_of_vertices; z++) { // Print Discover List printf("\n\n Discover List : "); for(i=0;i<=discover_top;i++) { printf("\t%d",discovered[i]); } // Print Visited List printf("\n Visited List : "); for(i=0;i<=visited_top;i++) { printf("\t%d",visited[i]); } // Find the vertices which connected with the new discover vertex pos=0; for(i=0; i<number_of_edges; i++) { if(edges[i][0] == discovered[discover_top]) { temp[pos]=edges[i][1]; pos++; } if(edges[i][1] == discovered[discover_top]) { temp[pos]=edges[i][0]; pos++; } } // Check whether the vertices which connected with the new discover vertex are already discover or not for(i=0; i<=discover_top; i++) { for(j=0;j<pos;j++) { if(discovered[i] == temp[j]) { for(k=j; k<pos1; k++) temp[k]=temp[k+1]; pos; } } } // Check whether the vertices which connected with the new discover vertex are already visited or not for(i=0; i<=visited_top; i++) { for(j=0;j<pos;j++) { if(visited[i] == temp[j]) { for(k=j; k<pos1; k++) temp[k]=temp[k+1]; pos; } } } // pos == 0, means that the vertices are connected with the last discover vertex are already discovered or visited. // So the last discovered vertex is removed from the discovered array and add into the visited array. if(pos == 0) { visited_top++; visited[visited_top]=discovered[discover_top]; discover_top; } // else find the lowest weighted vertex and add to it discovered array else { v=temp[0]; for(i=1; i<pos; i++) { if(v > temp[i]) { v=temp[i]; } } discover_top++; discovered[discover_top]=v; } } // After discover all the vertices add those vertices into visited array in decending order. while(discover_top != 1) { visited_top++; visited[visited_top]=discovered[discover_top]; discover_top; } } 
Figure 1 : Status of A changed to discovered.
Figure 2 : A has unknown two neighbors B and D, by convention B is visited first, i.e the status of B changes to discovered.
Figure 3 : B has two unknown neighbors C and D, by convention C is discovered first.
Figure 4 : C has only a single neighbor A which is already discovered so C is visited.
Figure 5 : The algorithm backtracks recursively to B, the next unknown neighbor is D, whose status is change to discovered.
Figure 6 : D has no neighbor, so D is visited.
Figure 7 : The algorithm backtracks recursively to B, which has no unknown neighbors, so B is visited.
Figure 8 : The algorithm backtracks to A which has no unknown neighbors so A is visited
Figure 9 : The connected component is visited so the algorithm moves to next component starting from E (because we are moving in increasing alphabetic order) so E is discovered.
Figure 10 : E has two unknown neighbors F and G, by convention we discover F
Figure 11 : F has no unknown neighbors so f is visited.
Figure 12 : The algorithm backtracks to E, which has G as the next unknown neighbor, g is discovered.
Figure 13 : The only neighbor of G is E, which is already discovered, so G is visited.
Figure 14 : The algorithm backtracks to E, which has no unknown neighbors left so E is visit.
ABOUT US QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries. Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions. Moreover, QuestionSolves.com provides solutions to your questions and assignments also.  
MORE TOPIC Windows Command UNIX Command IGNOU Assignment Solution IGNOU Question Paper Solution Solutions of Different Questions  
WHAT WE DO Website Devlopment Training Home Learning Provide BCA, MCA Projects Provide Assignment & Question Paper Solution  
CONTACT US
