CS201: Elementary Data Structures

Depth First Search is a graph traversal technique. The source is the first node to be visited, and then the we traverse as far as possible from each branch, backtracking when the last node of that branch has been visited. Here is the C implementation of Depth First Search using the Adjacency Matrix representation of graph.

The example graph we use for our program is :

C code :

#include <stdio.h>
#include <stdlib.h>
/*          ADJACENCY MATRIX                            */
int source,V,E,time,visited[20],G[20][20];
void DFS(int i)
{
    int j;
    visited[i]=1;
    printf(" %d->",i+1);
    for(j=0;j<V;j++)
    {
        if(G[i][j]==1&&visited[j]==0)
            DFS(j);
    }
}
int main()
{
    int i,j,v1,v2;
    printf("\t\t\tGraphs\n");
    printf("Enter the no of edges:");
    scanf("%d",&E);
    printf("Enter the no of vertices:");
    scanf("%d",&V);
    for(i=0;i<V;i++)
    {
        for(j=0;j<V;j++)
            G[i][j]=0;
    }
    /*    creating edges :P    */
    for(i=0;i<E;i++)
    {
        printf("Enter the edges (format: V1 V2) : ");
        scanf("%d%d",&v1,&v2);
        G[v1-1][v2-1]=1;

    }

    for(i=0;i<V;i++)
    {
        for(j=0;j<V;j++)
            printf(" %d ",G[i][j]);
        printf("\n");
    }
    printf("Enter the source: ");
    scanf("%d",&source);
        DFS(source-1);
    return 0;
}

Output:

Source: The Daily Programmer, http://www.thedailyprogrammer.com/2015/03/depth-first-search-adjacency-matrix.html
 This work is licensed under a Creative Commons Attribution 4.0 License.