Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction🎄
1.1.
Problem Description🗒️
2.
Approach 🤖
2.1.
Algorithm👽
2.2.
Sample Examples😄
2.3.
C++ Code⌨️
2.3.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What do you mean by a strongly connected graph?
3.2.
What is the run time complexity of the BFS algorithm?
3.3.
What are the applications of strongly connected components?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

Check if a Given Graph is Strongly Connected ( Kosaraju's BFS )🥷🏻

Author Manish Kumar
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction🎄

Hi Ninja🥷! In this article, we will learn to solve the problem of checking if a given graph is strongly connected ( Kosaraju's BFS ). A strongly connected component of a graph is a part in which there is a path from every vertex to another vertex. It is only valid in the case of directed graphs.

Check if a Given Graph is Strongly Connected ( Kosaraju's BFS )

We hope you will enjoy and have fun learning a hard-level DSA problem on graph data structure "Check if a given graph is strongly connected ( Kosaraju's BFS )".

Problem Description🗒️

Given a directed graph, we have to find out whether the graph is strongly connected or not. A directed graph is strongly connected if there is a path from every vertex to another vertex.

 

There are many algorithms to solve this problem, but one of the most efficient ones is Kosaraju’s BFS-based algorithm.

Approach 🤖

Following are the steps involved in Kosaraju’s BFS-based algorithm.

Approach

Algorithm👽

  • We do two BFS traversals of the given graph:
  • First, we Initialize all vertices as not visited.
  • Then we do a BFS traversal of a graph starting from any vertex, let's say vertex V.
  • After BFS traversal, if we cannot visit all vertices, then return false.
  • Second, We reverse all the edges present in the graph.
  • We Initialize all vertices as not visited in the reversed graph.
  • Then we repeat a BFS traversal of the reversed graph starting from the same vertex V.
  • After BFS traversal, if we cannot visit all vertices, then return false.
  • Otherwise, return true.

 

Sample Examples😄

Input:

input1

 

Output:

 

output1

 

Explanation:

 

We say a directed graph is strongly connected if there is a path from every vertex to another vertex.

Here, If we start from vertex 1, we get BFS as 1 2 3 4 5

After reversing the given graph, we get,

explanation

 

Again, starting with vertex 1, we get BFS as 1 0

Vertex 0 in the original graph and 2 3 4 5 in the reverse graph remain unvisited.

So, this graph is not strongly connected.
 

Input:

input 2

 

 

Output:

Given graph is strongly connected.

 

Explanation:

If we start from vertex 2, we get BFS as 2 4 3 5 0 6 1

After reversing the given graph, we get,

 

explanation2

 

Again, starting with vertex 2, we get BFS as 2 4 1 6 0 5 3

No vertex in the given and reversed graph remains unvisited.

So, this graph is strongly connected.

C++ Code⌨️

 

// Program to check if the given directed graph
// is strongly connected or not.
#include <bits/stdc++.h>
using namespace std;


class Graph
{
	int vertices; // To store no. of vertices
	list<int> *adjList;


	// Function to print DFS starting from v
	void BFSUtil(int v, bool visited[]);
	public:


	Graph(int V) { this->vertices = V; adjList = new list<int>[V];}
	~Graph() { delete [] adjList; }


	// Function to add an edge
	void addEdge(int v, int w);


	// Function that returns if the
	// graph is strongly connected or not.
	bool isStronglyConnected();


	// Function that returns reverse (or transpose)
	// of this graph
	Graph getTranspose();
};


	// A recursive function to print DFS starting from v
	void Graph::BFSUtil(int v, bool visited[])
	{
	// Creating a queue for BFS traversal
	list<int> queue;
	visited[v] = true;
	queue.push_back(v);


	list<int>::iterator i;


		while (!queue.empty())
		{
			// Dequeue a vertex from queue
			v = queue.front();
			queue.pop_front();
			for (i = adjList[v].begin(); i != adjList[v].end(); ++i)
			{
				if (!visited[*i])
				{
					visited[*i] = true;
					queue.push_back(*i);
				}
			}
		}
	}


	Graph Graph::getTranspose()
	{
		Graph g(vertices);
		for (int v = 0; v < vertices; v++)
		{
			list<int>::iterator i;
			for (i = adjList[v].begin(); i != adjList[v].end(); ++i)
			g.adjList[*i].push_back(v);
		}
		return g;
	}


	void Graph::addEdge(int v, int w)
	{
		adjList[v].push_back(w); 
	}


	// Function that returns true if graph
	// is strongly connected
	bool Graph::isStronglyConnected()
	{
		// Step 1: Mark all the vertices as not
		// visited (For first BFS)
		bool visited[vertices];
		for (int i = 0; i < vertices; i++)
		visited[i] = false;


		// Do BFS traversal starting from the first vertex.
		BFSUtil(0, visited);


		// If BFS traversal doesn’t visit all vertices
		// return false.
		for (int i = 0; i < vertices; i++)
		if (visited[i] == false)
		return false;


		//Create a reversed graph
		Graph gr = getTranspose();


		// Step 4: Mark all the vertices as not
		// visited (For second BFS)
		for(int i = 0; i < vertices; i++)
		visited[i] = false;


		gr.BFSUtil(0, visited);


		// If all vertices are not visited in the second DFS
		//return false
		for (int i = 0; i < vertices; i++)
		if (visited[i] == false)
		return false;


		return true;
	}


	// Driver program to test the above functions
	int main()
	{
		Graph g1(7);
		g1.addEdge(0, 1);
		g1.addEdge(1, 2);
		g1.addEdge(2, 3);
		g1.addEdge(3, 0);
		g1.addEdge(2, 4);
		g1.addEdge(4, 2);
		g1.addEdge(4, 5);
		g1.addEdge(5, 6);
		g1.addEdge(6, 4);

		g1.isStronglyConnected()?cout<<"Yes":cout<<"No";
		return 0;
	}

 

Output: 

Yes

 

Complexity Analysis

Time Complexity: O(V+E), where V and E are the numbers of vertices and edges, respectively. Time taken by this algorithm if the graph is represented using adjacency matrix representation is the same as BFS traversal.

Space Complexity: O(V), Where V is the number of vertices in the graph. We have to maintain a visited array and list of size V.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What do you mean by a strongly connected graph?

A strongly connected graph is a graph in which there is a path from every vertex to another vertex. It is only valid in the case of directed graphs.

What is the run time complexity of the BFS algorithm?

Breadth First Search runs in O(V+E), where V is the number of vertices and E is the number of Edges.

What are the applications of strongly connected components?

Maps of connected places

Vehicle routing applications

Model-checking in formal verification

Conclusion

In this blog, we learned Kosaraju’s BFS algorithm to check if a graph is strongly connected or not. We went through the algorithm and implemented the code. We also analysed the time and space complexities of our code. We hope you enjoyed reading our blog on Kosaraju’s BFS algorithm to check if a graph is strongly connected or not. To read other graph-related topics, refer to these pages:  star graphnodes within k-distanceminimum edges between two vertices etc.

 

Refer to our Guided Path on Coding Ninjas Studio to upskill ourselves in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! But suppose we have just started our learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, we must look at the problemsinterview experiences, and interview bundles for placement preparations.
 

Nevertheless, we may consider our paid courses to give our career an edge over others!

Do upvote this blog if you find it helpful and engaging!

Happy Learning!!

Previous article
Minimum Operations to Convert Number
Next article
Check if the Graph can be Divided into Two Cliques
Live masterclass