C Program for Depth - First Search in Graph (Adjacency Matrix)

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 : 

Example Graph




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: 

Output
Output

Share on Google Plus
Love what you read? Share this article among your friends and comment your thoughts below. We'd love to hear from you! If you'd like to read more such articles, follow The Daily Programmer on Twitter @programmerdaily and receive fresh, well-researched content delivered to your feed.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment