C Program to Check the Connectivity of Graph Using DFS

This is a C Program to check the connectivity of directed graph using DFS. Depth-first search is a systematic way to find all the vertices reachable from a source vertex, s. Historically, depth-first was first stated formally hundreds of years ago as a method for traversing mazes. Like breadth-first search, DFS traverse a connected component of a given graph and defines a spanning tree. The basic idea of depth-first search is this: It methodically explore every edge. We start over from different vertices as necessary. As soon as we discover a vertex, DFS starts exploring from it

Here is source code of the C Program to Check the Connectivity of Graph Using DFS. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#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);
```
```
        }
```
```
}
```
```
int main(int argc, char **argv) {
```
```
    int i, j, count = 0;
```

    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");

```
    return 0;
```
```
}
```

Output:

$ gcc ConnectivityUsingDFS.c
$ ./a.out
 
Enter number of vertices: 8
Enter the adjacency matrix:
0 1 0 0 0 0 0 1 0 
1 0 1 0 0 0 0 1 0 
0 1 0 1 0 1 0 0 1 
0 0 0 1 0 1 0 0 0  
0 0 1 0 1 0 1 0 0
0 0 0 1 0 1 0 1 1  
1 1 0 0 0 0 1 0 1  
0 0 1 0 0 0 1 1 0  
 
1->2
2->4
4->3
3->6
3->8
8->5
5->7
 
Graph is connected

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Check the Connectivity of Graph Using BFS

» Next - Inorder Traversal of a Binary Tree without using Recursion in C

Related Posts:

Recommended Articles: