Algorithm and Program for Depth First Search in C

Depth First Search is one of the standard ways to traverse a graph . Depth First Search traversal is used by most of the Graph algorithms .

Depth First Search :

The Depth First Search ( DFS ) , as its name implies , is to search deeper in the graph , whenever possible . The edgesare explored out of the most recently discovered vertex v that still has unexplored edges leaving it . When all of V's edges have been explored , the search backtracks to explore edges leaving the vertex from which v was discovered . This process continues until we have disocvered all the vertices that are reachable from the source vertex . This algorithm also works on both directed as well as on undirected graphs .
     To keep track of the progress , the DFS also uses the same coloring scheme as described for BFS . In addition the DFS makes uses of a stack structure to maintain the order in which the vertices are to be processed , instead of queue
The below algorithm summarizes various steps required to implement the DFS

Depth First Search Iterative (adj,n,s): 

Here adj is the adjacency list of the graph with n vertices , and vertex s is the source vertex . This algorithm uses a stack STACK , and linear array color of size n , to keep track of the progress of DFS . Its also uses local variables u and ptr .

Also check : Threaded Binary Tree Structures

Depth First Search (DFS) Algorithm :

 BEGIN
    for i=1 to n by 1 do
        set color[i]=WHITE
    endfor
    Set color[s]=GRAY
    CALL createstack(stack)
    Call push(stack,s)
    while(Stack is not empty) do
        Set u=peek(stack)
        Set ptr=adj[u]
        while(ptr!=NULL) do
            if(color[prt->info]=WHITE) then
                Set color[ptr->info]=GRAY
                Call push(&stack,ptr->info)
                Set u=ptr->info
                Set ptr=adj[u]
            else
                Set ptr=ptr->next
            endif
        endwhile
        Call pop(&stack,u)
        Print :u
        Set color[u]=BLACK
    endwhile
End

 Advantages of DFS :

• It doesn't required to store neighbouring nodes
• If DFS finds solution without exploring much in path then the time and space it takes will be very less .

Disadvantages of DFS :

• The disadvantage of DFS is that there is a possibility that it may go down the left most path forever . One solution to this problem is to impose a cutoff depth on the search .
• DFS is not guaranteed to find the solution .
• It never guaranteed to find a minimal solution if more than one solution exists .

Also check : Binary Tree Traversal and Tree Iterations

Efficiency :

The time and space analysis of DFS differs according to its application area . DFS is used to traverse an entire graph and takes O(|V|+|E|) time . In these applications it also uses space O(|V|) in the worst case to store the stack of vertices on the current search path as well as the set of already visited vertices .

Program for Depth First Search in C :

#include<stdio.h>
#include<conio.h>
#define size 20
int a[10][10],vertex[10],n,e;
//STACK FUNCTIONS
#define bottom -1
int stack[size],top=bottom;
int stackempty()
{
    return (top==bottom)?1:0;
}
int stackfull()
{
    return (top==size-1)?1:0;
}
void push(int item)
{
    if(stackfull())
        printf("Stack is full");
    else
        stack[++top]=item;
}
int pop()
{
    if(stackempty())
    {
        printf("Stack is empty");
        return -1;
    }
    else
        return stack[top--];
}
int peep()
{
    if(stackempty())
    {
        printf("Stack is empty");
        return -1;
    }
    else
        return stack[top];
}
//j is unvisited adjacent vertex to i
int adjvertex(int i)
{
    int j;
    for(j=0;j<n;j++)
        if(a[i][j]==1&&vertex[j]==0)
        return j;
    return n;
}
int visitall()
{
    int i;
    for(i=0;i<n;i++)
        if(vertex[i]==0)
        return 0;
    return 1;
}
//function for DFS
void dfs()
{
    int i,j,k,cur=0;
    for(i=0;i<n;i++)
        vertex[i]=0;
    printf("DFS path => V%d",cur+1);
    push(cur);
    vertex[cur]=1;
    while(!visitall())
    {
        do
        {
            cur=adjvertex(peep());
            if(cur==n) pop();
        }
        while(cur==n&&!stackempty());
        if(stackempty())
        {
            printf("Graph is disconnected");
            break;
        }
        if(cur!=n)
        {
            printf("V%d",cur+1);
            push(cur);
            vertex[cur]=1;
        }
    }
}
void main()
{
    int i,j,k;
    clrscr();
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
        a[i][j]=0;
    printf("Enter no. of vertices & edges of undirected graph:");
    scanf("%d%d",&n,&e);
    printf("Enter edges as pair of vertices");
    for(k=1;k<=e;k++)
    {
        printf("Edge %d =>",k);
        scanf("%d%d",&i,&j);
        a[i-1][j-1]=1;
    }
    dfs();
    getch();
}

Final Words !
If I had missed anything please let me know through comments . Share the post with your friends through Facebook . Also share your idea through comments .