In this article, we will discuss how to find the connected components in a graph. Connected components mean each node in a subgraph is connected with a path. If you refer to the above graph, node 5 and 6 are not connected to any other nodes and the same is true with node 7
Now let’s see how to find the connected components in a graph. Normally a graph can be traversed using a Breadth-first-search(BFS) or Depth-first-search(DFS). For this case, we will find the connected components using a DFS approach. To learn about Depth-first-search please refer to this article
Steps to find the connected components in a graph
- Start a DFS search from any node in the graph
- The number of times DFS is performed in the graph is the number of connected components available
Yeah, simple right, let's see how this works. Assume we store our visited nodes in a Set<Node>, when we start our DFS from node 1, we will visit the nodes like [1,2,3,4], after which we do not have any neighbours to traverse, so now count is 1. The next iteration goes to the non-visited node which can be node 5, and the result will be [5,6], no other neighbours to visit, now the count becomes 2. The next iteration will go to node 7, the result looks like [7] and the final count becomes 3. Voila we were able to find the connected components in a graph
Below is the code snippet in Java
