Dfs implementation in c
?
0 likes?86 views
This C program uses depth-first search (DFS) to determine if a graph represented by an adjacency matrix is connected. It takes user input for the number of vertices and adjacency matrix, performs DFS starting at vertex 1, and counts the reached vertices. If the count equals the number of vertices, the graph is connected, otherwise it is not connected.
![?
#include<stdio.h>
#include<conio.h>
int?a[20][20],reach[20],n;
void?dfs(int?v)
{
?int?i;
?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?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?Graph?is?connected");
?else
??printf("n?Graph?is?not?connected");
?getch();](https://image.slidesharecdn.com/dfs-161127212033/85/Dfs-implementation-in-c-1-320.jpg)