Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Brute Force Method
3.
Types of Graphs
3.1.
Directed Graph
3.2.
Undirected Graph
4.
Kosaraju's DFS
5.
Implementation
5.1.
In CPP
5.2.
In Java
6.
6.1.
What is the Brute Force Method?
6.2.
What are the different types of Graphs?
6.3.
What are directed graphs?
6.4.
What are undirected graphs?
6.5.
What is Kosaraju's algorithm?
7.
Conclusion
Last Updated: Mar 27, 2024

# Check if a Graph is Strongly Connected

## Introduction

A component is said to be strongly connected if we can access every vertex from every other vertex in that component (SCC). An SCC is always a single node.

We have two algorithms for finding SCCs, Tarjan's and Kosaraju's algorithm. In this post, we will look at Kosaraju's algorithm. To discover more about Tarjan's algorithm, go to Coding Ninjas website or simply click here. So let's begin.

## Brute Force Method

The Floyd Warshall technique may be used to determine the distance between any two vertices and then verify if the distance between any two pairs is infinite. Except for the possibility of a self-loop, this indicates that both are unreachable. However, it has a temporal complexity of around O(V^3), which we cannot afford in most circumstances.

## Types of Graphs

Two different graph types exist. As follows:

• Directed Graph
• Undirected Graph

### Directed Graph

directed graph, also known as a digraph, consists of a set of vertices and a group of directed edges, each of which links a pair of ordered vertices. A directed edge is one that originates at the first vertex of the pair and terminates at the second vertex.

### Undirected Graph

An undirected graph is a collection of linked nodes with only bidirectional edges. An undirected network is another name for an undirected graph. Edges in an undirected graph do not have a clear direction. Thus, it is known as an undirected graph.

Note

If every vertex in a graph can be reached from every other vertex, the graph is said to be strongly connected. An arbitrary directed graph is divided into strongly connected subgraphs by its strongly connected components.

If there is a path connecting each pair of the graph's vertices in each direction, a directed graph is said to be strongly connected. The first vertex in the pair has a path leading to the second, and the second vertex has a path leading to the first.

You can also read Detect cycle in an undirected graph here.

## Kosaraju's DFS

The depth-first search algorithm is the foundation of Kosaraju's method, which was twice implemented.

The straightforward approach by Kosaraju algorithm that performs two DFS traversals of the graph is as follows:

• Set each vertex's initial state to unvisited.
• Perform a DFS traversal of the graph beginning at any vertex v. Return false if the DFS traversal doesn't reach every vertex.
• Invert each arc (or find transpose or reverse of the graph)
• Mark each vertex in the reversible graph as unvisited.
• Beginning with the same vertex v, do a DFS traversal of the inverted graph. Return false if DFS traversal doesn't reach every vertex. If not, return true.

Now, let's check whether this graph is strongly connected or not;

## Implementation

### In CPP

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
int search, destination ;
};

class Graph
{
Public:

Graph(vector<Edge> const &edges, int n)
{

for (auto &edge: edges) {
}
}
};

void DFS(Graph const &graph, int v, vector<bool> &visited)
{
visited[v] = true;
for (int u: graph.adjList[v])
{
if (!visited[u]) {
DFS(graph, u, visited);
}
}
}

bool isStronglyConnected(Graph const &graph, int n)
{

for (int i = 0; i < n; i++)
{
vector<bool> visited(n);

DFS(graph, i, visited);

if (find(visited.begin(), visited.end(), false) != visited.end()) {
return false;
}
}

return true;
}

int main()
{
vector<Edge> edges = {
{0, 4}, {1, 0}, {1, 2}, {2, 1}, {2, 4},
{3, 1}, {3, 2}, {4, 3}
};

int n = 5;

Graph graph(edges, n);

if (isStronglyConnected(graph, n)) {
cout << "This graph is strongly connected";
}
else {
cout << "This graph is not strongly connected";
}

return 0;
}``````

Output:

``This graph is strongly connected``

Time Complexity: If the graph is represented using an adjacency list, the above approach has the same time complexity as Depth First Search, which is O(V+E).

### In Java

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class edge
{
int source, destination ;

public edge(int source, int destination )
{
this.source = source;
this.destination  = destination ;
}
}

class Graph
{

List<List<Integer>> adjList = null;

Graph(List<Edge> edges, int n)
{
adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
}

for (Edge edge: edges)
{
int search = edge.source;
int destination  = edge.destination ;

}
}
}

class Main
{
private static void DFS(Graph graph, int v, boolean[] visited)
{
visited[v] = true;

for (int u: graph.adjList.get(v))
{
if (!visited[u]) {
DFS(graph, u, visited);
}
}
}

public static boolean isStronglyConnected(Graph graph, int n)
{
for (int i = 0; i < n; i++)
{
boolean[] visited = new boolean[n];

DFS(graph, i, visited);

for (boolean b: visited)
{
if (!b) {
return false;
}
}
}

return true;
}

public static void main(String[] args)
{
List<Edge> edges = Arrays.asList(
new Edge(0, 4), new Edge(1, 0), new Edge(1, 2), new Edge(2, 1),
new Edge(2, 4), new Edge(3, 1), new Edge(3, 2), new Edge(4, 3)
);

int n = 5;

Graph graph = new Graph(edges, n);

if (isStronglyConnected(graph, n)) {
System.out.println("This graph is strongly connected");
}
else {
System.out.println("This graph is not strongly connected");
}
}
}``````

Output:

``This graph is strongly connected``

Time Complexity: The above method has the same time complexity as that of Kosaraju algorithm Depth First Search, which is O(V+E) only if the graph is represented using an adjacency list.

## Frequently Asked Questions

### What is the Brute Force Method?

Brute force algorithms are exactly what they resemble- simple solutions to problems that rely on computer power alone and exhaust all possibilities rather than using cutting-edge approaches to increase efficiency.

### What are the different types of Graphs?

There are two different types of graphs: Directed and Undirected graphs.

### What are directed graphs?

A directed graph mainly consists of a set of vertices and a group of directed edges, each of which links a pair of ordered vertices.

### What are undirected graphs?

An undirected graph is a collection of linked nodes with only bidirectional edges. An undirected network is another name for an undirected graph.

### What is Kosaraju's algorithm?

The Kosaraju-Sharir method, also known as Kosaraju's algorithm, is a linear time approach for determining the strongly connected components of a directed graph.

## Conclusion

In this article, we learned about Kosaraju's Algorithm and dry run with various examples to have a clear idea.

After reading about Kosaraju's Algorithm, are you not feeling excited to read/explore more articles on the topic of Ruby? Don't worry; Coding Ninjas has you covered. To learn, see Multithreading in Python, Descriptors in Python, and BorderLayout in Java.

Recommended Problem - K Closest Points To Origin

Refer to our Guided Path on Code studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more!

Do upvote our blogs if you find them helpful and engaging!

Live masterclass