DFS (Depth-first search) Algorithm: Data Structure

What is DFS (Depth-first search)?

The depth first search is a graph traversal algorithm. The idea behind this algorithm is backtracking and it is a kind of recursive algorithm. In the depth first search, it contains the exhaustive searches of all the nodes if possible, else by the concept of backtracking.

If we describe the mean of backtracking, which is when we are moving ahead on the current path and we find there is no more node to traverse, then we need to backtrack on the same path to find the nodes for traversing. As we said that the DFS is a kind of recursive algorithm so we can implement it with a help of stacks.

Now we are going to discuss the idea of DFS as follows:

• We need to start from the starting node and push the adjacent node into the stack
• Then we need to pop a node from the stack and push its adjacent node into the stack
• We will repeat this process until the stack is empty. We should check the nodes which we have visited are marked. This thing helps us to ensure whether the node is visited or not.

Depth First Search Example

DFS Algorithm

 Push the stating vertex into the stack.
Mark it as visited.
Display it.
If( Stack[Top] has adjacent unvisited vertex)
{          
            Visit the adjacent unvisited vertex and Mark it as visited.
            Push it into Stack.
            Display it.
}
Else
{
            Pop top element of Stack.
}
(Repeat 2nd point until Stack is empty)     

DFS Program in C language

 #include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    struct node *next;
    int vertex;
}node;
node *G[20];  
// Heads of linked list
int visited[20];
int n;
void read_graph();
// Create adjacency list
void insert(int, int); 
// Insert an edge (vi, vj) in te adjacency list
void DFS(int);
void main()
{
    int i;
    read_graph();
    // Initialised visited to 0
            for(i = 0; i<n; i++)
        visited[i]  =  0;
    DFS(0);
}
void DFS(int i)
{
    node *p;
            printf("\n%d",i);
    p  =  G[i];
    visited[i]  =  1;
    while(p  != NULL)
    {
       i  =  p -> vertex;
               if(!visited[i])
            DFS(i);
        p  =  p -> next;
    }
}
void read_graph()
{
    int i, vi, vj, no_of_edges;
    printf("Enter number of vertices:");
            scanf("%d",&n);
    // Initialise G[] with a null
            for( i = 0; i<n; i++)
    {
        G[i]  =  NULL;
        // Read edges and insert them in G[]
                        printf("Enter number of edges:");
           scanf("%d", &no_of_edges);
           for(i = 0; i<no_of_edges; i++)
        {
           printf("Enter an edge(u,v):");
                                    scanf("%d%d", &vi,&vj);
                                    insert(vi, vj);
        }
    }
}
void insert(int vi, int vj)
{
    node *p,*q;
            // acquire memory for the new node
            q  =  (node*)malloc(sizeof(node));
    q -> vertex  =  vj;
    q -> next  =  NULL;
    //insert the node in the linked list number vi
    if(G[vi] == NULL)
        G[vi]  =  q;
    else
    {
        // Go to end of the linked list
        p  =  G[vi];
                        while(p -> next != NULL)
           p  =  p -> next;
        p -> next  =  q;
    }
} 

Output

Complexity of DFS

The time complexity of DFS is O(V+E), where V is number of vertex and E is number of edges in the graph.

Applications of DFS

• DFS is used to find the minimum spanning tree
  • Used to detect the cycle in the graph
  • Used to find the path between two points.