/* Depth first search algorithm extends the current path as far as possible before backtracking to the lastchoice point and trying the next alternative path. Depth first search may fail to find a solution if it enters acycle in the graph. This can be avoided if we never extend a path to a node which it already contains.*/
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v)
{
int i;
Also Read : Program for implementing Breadth First Search
reach[v]=1;
for(i=1;i<=n;i++)
if(a[v][i] && !reach[i])
{
printf(“\n %d->%d”,v,i);
dfs(i);
}
}
void main()
{
int i,j,count=0;
clrscr();
printf(“\n \n Enter number of vertices:”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
}
printf(“\n Enter the adjacency matrix:\n”);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(“%d”,&a[i][j]);
dfs(1);
printf(“\n “);
for(i=1;i<=n;i++)
{
if(reach[i])
count++;
}
if(count==n)
printf(“\n End”);
else
printf(“\n Graph is not connected”);
getch();
}
Output:
You can check my other blog - CatchUpdates.com
You can connect with me on Instagram Or Quora And Linkedin as well.
- MongoDB Operators Tutorial – What are Different Operators Available? - October 5, 2019
- MongoDB Projection Tutorial : Return Specific Fields From Query - March 9, 2019
- MongoDB Index Tutorial – Create Index & MongoDB Index Types - July 6, 2018