DEPTH FIRST SEARCH (DFS)

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.

Depth First Search Programming in C
 #include #include //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 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--; } }

 DEPTH FIRST SEARCH IN DIRECT GRAPHS

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.

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

WHAT WE DO