DEPTH FIRST SEARCH (DFS)

If you have any queries please leave a message here
Your Message
×


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<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<pos-1; 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<pos-1; 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--;
}
}



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.



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


Follow Us