Algorithms for Coding Interviews in C++/

...

/

Solution: Print all Connected Components of a Graph

Solution: Print all Connected Components of a Graph

This review provides a detailed analysis of the solution to print all connected components of a graph.

We'll cover the following...

Solution #1: Simple Depth First Traversal

Press + to interact
main.cpp
Graph.cpp
Graph.h
#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: ...