C Program to Check if a Graph is Strongly Connected or Not

This is a C Program to find the connected components of the undirected graph. This can be done using depth first search. If the number of connected components is greater than one graph is weakly connected else its strongly connected.

Here is source code of the C Program to Check Whether a Graph is Strongly Connected or Not. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <string.h>
```
```
#include <stdbool.h>
```
```
 
```
```
#define ROW 5
```
```
#define COL 5
```
```
int i, j, k;
```

// A function to check if a given cell (row, col) can be included in DFS

int isSafe(int M[][COL], int row, int col, bool visited[][COL]) {

    return (row >= 0) && (row < ROW) && // row number is in range

            (col >= 0) && (col < COL) && // column number is in range

            (M[row][col] && !visited[row][col]); // value is 1 and not yet visited

```
}
```
```
 
```

// A utility function to do DFS for a 2D boolean matrix. It only considers

```
// the 8 neighbors as adjacent vertices
```

void DFS(int M[][COL], int row, int col, bool visited[][COL]) {

    // These arrays are used to get row and column numbers of 8 neighbors

```
    // of a given cell
```

    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

```
 
```
```
    // Mark this cell as visited
```
```
    visited[row][col] = true;
```
```
 
```

    // Recur for all connected neighbours

```
    for (k = 0; k < 8; ++k)
```

        if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))

            DFS(M, row + rowNbr[k], col + colNbr[k], visited);

```
}
```
```
 
```

// The main function that returns count of islands in a given boolean

```
// 2D matrix
```
```
int countIslands(int M[][COL]) {
```

    // Make a bool array to mark visited cells.

    // Initially all cells are unvisited

```
    bool visited[ROW][COL];
```

    memset(visited, 0, sizeof(visited));

```
 
```

    // Initialize count as 0 and travese through the all cells of

```
    // given matrix
```
```
    int count = 0;
```
```
    for (i = 0; i < ROW; ++i)
```
```
        for (j = 0; j < COL; ++j)
```

            if (M[i][j] && !visited[i][j]) // If a cell with value 1 is not

            { // visited yet, then new island found

                DFS(M, i, j, visited); // Visit all cells in this island.

                ++count; // and increment island count

```
            }
```
```
 
```
```
    return count;
```
```
}
```
```
 
```

// Driver program to test above function

```
int main() {
```
```
    int M[][COL] = { { 1, 1, 0, 0, 0 },
```
```
                     { 0, 1, 0, 0, 1 },
```
```
                     { 1, 0, 0, 1, 1 },
```
```
                     { 0, 0, 0, 0, 0 },
```
```
                     { 1, 0, 1, 0, 1 }
```
```
                   };
```
```
 
```
```
    if(countIslands(M)>1)
```
```
    {
```

        printf("Graph is weakly connected.");

```
    }
```
```
    else
```
```
    {
```

        printf("Graph is strongly connected.");

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

Output:

$ gcc CheckStronglyConnectedGraph.c
$ ./a.out
 
Graph is weakly connected.

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

« Prev - C Program to Create a Balanced Binary Tree of the Incoming Data

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

Related Posts:

Recommended Articles: