Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Print all the Connected Components of a Graph

Understand how to print all connected components in a graph by using a visited array and traversal methods. Learn to detect unvisited nodes and handle multiple components with a time complexity of O(V + E). This lesson helps you implement efficient graph traversal to solve connected components problems.

We'll cover the following...

Solution

Java
class PrintComp {
 public static void printConnectedComponents(Graph g) {
  int num_vertices = g.getVertices();
  boolean[] visited = new boolean[num_vertices];
  for (int i = 0; i < num_vertices; ++i) {
   if (!visited[i]) {
    utilityFunction(g, i, visited);
    System.out.println();
   }
  }
 }
 public static void utilityFunction(Graph g, int v, boolean visited[]) {
  visited[v] = true;
  System.out.print(v + " ");
  LinkedList < Integer > Llist[];
  Llist = g.getAdj();
  for (int i: Llist[v]) {
   if (!visited[i]) {
    utilityFunction(g, i, visited);
   }
  }
 }
}
class Main {
 public static void main(String args[]) {
  Graph g = new Graph(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);
  System.out.println("The connected components are:");
  PrintComp.printConnectedComponents(g);
 }
}

Explanation

We can solve this problem simply by iterating through the graph. Nothing too tricky going on here. We make a visited array whose values are by default set to false. Now, if in the end there are nodes that are still marked as unvisited ...