C Program to Check the Connectivity of Graph Using BFS

This is a C Program to check the connectivity of directed graph using BFS. Breadth-first search is a way to find all the vertices reachable from the a given source vertex, s. Like depth first search, BFS traverse a connected component of a given graph and defines a spanning tree. Intuitively, the basic idea of the breath-first search is this: send a wave out from source s. The wave hits all vertices 1 edge from s. From there, the wave hits all vertices 2 edges from s. Etc. We use FIFO queue Q to maintain the wavefront: v is in Q if and only if wave has hit v but has not come out of v yet.

Here is source code of the C Program to Check the Connectivity of Graph Using BFS. 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], q[20], visited[20], n, i, j, f = 0, r = -1;

```
void bfs(int v) {
```
```
    for (i = 1; i <= n; i++)
```
```
        if (a[v][i] && !visited[i])
```
```
            q[++r] = i;
```
```
    if (f <= r) {
```
```
        visited[q[f]] = 1;
```
```
        bfs(q[f++]);
```
```
    }
```
```
}
```
```
int main(int argc, char **argv) {
```
```
    int v = 1, count = 0;
```

    printf("\n Enter the number of vertices:");

```
    scanf("%d", &n);
```
```
    for (i = 1; i <= n; i++) {
```
```
        q[i] = 0;
```
```
        visited[i] = 0;
```
```
    }
```

    printf("\n Enter graph data in matrix form:\n");

```
    for (i = 1; i <= n; i++)
```
```
        for (j = 1; j <= n; j++)
```
```
            scanf("%d", &a[i][j]);
```
```
    bfs(v);
```
```
    for (i = 1; i <= n; i++)
```
```
        if (visited[i])
```
```
            count++;
```
```
    if (count == n)
```

        printf("\n Graph is connected");

```
    else
```

        printf("\n Graph is not connected");

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

Output:

$ gcc ConnectivityUsingBFS.c
$ ./a.out
 
Enter the number of vertices: 8
Enter graph data in matrix form:
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 
 
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 if a Graph is Strongly Connected or Not

» Next - C Program to Check the Connectivity of Graph Using DFS

Related Posts:

Recommended Articles: