C Program for Depth-First Search in a Graph
There are many ways to traverse a graph; this article focuses on depth-first. This approach seeks a solution by going to the nodes furthest from the starting point.
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.
Last modified: Monday, November 16, 2020, 8:18 PM