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

Solution: Print all Connected Components of a Graph

Explore methods to identify and print all connected components of a graph using depth-first traversal and Kosaraju’s algorithm. Understand each approach's implementation and time complexity to strengthen your grasp on graph algorithms in C++.

We'll cover the following...

Solution #1: Simple Depth First Traversal

C++
#include "Graph.h"
void Graph::utilityFunction(int v, vector <bool>& visited) {
  visited[v] = true;
  cout << v << " ";
  list <int> ::iterator i;
  for (i = adjacencyList[v].begin(); i != adjacencyList[v].end(); ++i)
    if (!visited[ * i])
      utilityFunction( * i, visited);
}
void Graph::printConnectedComponents() {
  vector <bool> visited(this -> vertices, false);
  for (int v = 0; v < this -> vertices; v++) {
    if (visited[v] == false) {
      utilityFunction(v, visited);
      cout << endl;
    }
  }
}
int main() {
  Graph g(7);
  g.addEdge(0, 1);
  g.addEdge(1, 2);
  g.addEdge(3, 4);
  g.addEdge(5, 3);
  g.addEdge(5, 6);
  g.addEdge(3, 6);
  cout << "The connected components are:" << endl;
  g.printConnectedComponents();
  return 0;
}

We can solve this problem simply by iterating through the graph. Nothing too tricky going on here. We already made a visited array for DFS. Now, if in the end there are nodes that are still marked as unvisited, simply print the visited nodes and call the utility function again. Start traversal for these unvisited nodes, but keep in mind that now we are dealing with a different component of the same graph.

Time complexity

Since we are simply traversing the whole graph the time complexity will be the total number of vertices and edges: ...