Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Check if a Graph is Strongly Connected

Explore how to verify if a graph is strongly connected by applying depth-first and breadth-first traversals, along with using the graph's transpose. Understand the step-by-step process of initializing vertices, performing traversals, and interpreting results to confirm strong connectivity efficiently in C++.

We'll cover the following...

Solution: Recursion

C++
#include "Graph.h"
void Graph::utilityFunction(int v, vector <bool>& visited) {
  visited[v] = true;
  list <int> ::iterator i;
  for (i = adjacencyList[v].begin(); i != adjacencyList[v].end(); ++i)
    if (visited[ * i] == false)
      utilityFunction( * i, visited);
}
bool Graph::isStronglyConnected() {
  vector <bool> visited(this -> vertices);
  for (int i = 0; i < this -> vertices; i++)
    visited[i] = false;
  // check graph for unvisited vertices
  utilityFunction(0, visited);
  
  // if graph has any unvisited nodes return false
  for (int i = 0; i < this -> vertices; i++)
    if (visited[i] == false)
      return false;
  // NOW CHECK FOR TRANSPOSED GRAPH 
  
  // find the transpose of the graph
  Graph gTranspose = getTranspose();
  for (int i = 0; i < this -> vertices; i++)
    visited[i] = false;
 
  // check transposed graph for non visited vertices
  gTranspose.utilityFunction(0, visited);
  
  // if transpose of graph has any unvisited nodes return false
  for (int i = 0; i < this -> vertices; i++)
    if (visited[i] == false)
      return false;
  return true;
}
int main() {
  Graph g1(5);
  g1.addEdge(0, 1);
  g1.addEdge(1, 2);
  g1.addEdge(2, 3);
  g1.addEdge(3, 0);
  g1.addEdge(2, 4);
  g1.addEdge(4, 2);
  
  if(g1.isStronglyConnected())
    cout << "Yes Graph1 is strongly connected\n"; 
  else
    cout << "No Graph1 is not strongly connected\n";
  Graph g2(4);
  g2.addEdge(0, 1);
  g2.addEdge(1, 2);
  g2.addEdge(2, 3);
  
  if(g2.isStronglyConnected())
    cout << "Yes Graph2 is strongly connected\n"; 
  else
    cout << "No Graph2 is not strongly connected\n";
  return 0;
}

The solution might look confusing at first, but the logic behind it is pretty straight forward.

Start thinking about how Graph Traversal is implemented. Initialize all vertices as not visited, like we used to do in Depth-First Graph Traversal or Breadth First Graph Traversal. You can start from any arbitrary vertex vv ...