Find Connected Components

Write a program to find connected components in the graph.

Example 1:

Input: n=8,edges={{1,2},{1,3},{4,5},{4,6},{7,8}}
Output: {{1,2,3},{4,5,6},{7,8}}

Approach 1: Using Depth First Search (DFS).

Java

import java.util.ArrayList;

public class DFSConnectedComponent {
    // visited list
    public static ArrayList<Integer> visited = new ArrayList<>();

    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int v = 9;
        for (int i = 0; i < v; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 4, 5);
        addEdge(adj, 4, 6);
        addEdge(adj, 7, 8);
        // Iterate all connected component
        for (int i = 1; i < v; i++) {
            // if not visited
            if (visited.indexOf(i) == -1) {
                findConnectedComponentUsingDFS(adj, i);
                System.out.println();
            }
        }
    }

    /**
     * @Desc: connected component using DFS
     * @param source
     */
    private static void findConnectedComponentUsingDFS(
            ArrayList<ArrayList<Integer>> g, int source) {
        // mark node as visited
        visited.add(source);
        System.out.print(source + " ");
        // Iterate through adjacency list
        for (int child : g.get(source)) {
            // if node not visited
            if (visited.indexOf(child) == -1) {
                // call dfs
                findConnectedComponentUsingDFS(g, child);
            }
        }

    }

    private static void addEdge(ArrayList<ArrayList<Integer>> g,
                 int u, int v) {
        // undirected graph
        g.get(u).add(v);
        g.get(v).add(u);
    }
}

//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges

C++

#include <bits/stdc++.h>
using namespace std;
//adjacency list
vector<int> adj[1001];
//visited array to hold
//which node is visit and which
//is not
bool visited[100001];
//function to add the edge
//into the adjacency list
void addEdge(int u,int v)
{
    //undirected graph
    adj[u].push_back(v);
    adj[v].push_back(u);
}
//function to find DFS traversal of
//a graph
void dfsTraversal(int node)
{
    //mark the current node as
    //visited
    visited[node]=1;
    //print the current node
    cout<<node<<" ";
    //iterate through adjacency list
    //of the current node
    for(int child:adj[node])
     {
         //if node visited then call the 
         //dfs for it
         if(visited[child]==0)
           {
               dfsTraversal(child);
           }
     }
}
int main()
{
  int n=8;
  int edges=5;
  addEdge(1,2);
  addEdge(1,3);
  addEdge(4,5);
  addEdge(4,6);
  addEdge(7,8);
  cout<<"Connected componets are\n";
  for(int i=1;i<=n;i++)
    {
        if(visited[i]==0)
          {
              dfsTraversal(i);
              cout<<"\n";
          }
          
    }
   return 0;
}
//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges

Approach 2: Using  Breadth-First Search (BFS).

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BFSConnectedComponent {
    // visited list
    public static ArrayList<Integer> visited = new ArrayList<>();

    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int v = 9;
        for (int i = 0; i < v; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 4, 5);
        addEdge(adj, 4, 6);
        addEdge(adj, 7, 8);
        // Iterate all connected component
        for (int i = 1; i < v; i++) {
            // if not visited
            if (visited.indexOf(i) == -1) {
                findConnectedComponentUsingBFS(adj, i);
                System.out.println();
            }
        }
    }

    /**
     * @Desc: Method used for BFS
     * @param graph
     */
    private static void findConnectedComponentUsingBFS(
                ArrayList<ArrayList<Integer>> g, int source) {
        // create queue
        Queue<Integer> queue = new LinkedList<>();
        // add node into queue
        queue.add(source);
        // make visited node
        visited.add(source);
        // Iterate till queue is not empty
        while (!queue.isEmpty()) {
            // get front value from queue and pop front
            int v = queue.poll();
            // print the front element of the queue
            System.out.print(v + " ");
            // iterate through the adjacency list
            // of the popped element
            for (Integer child : g.get(v)) {
                // If not visited
                if (visited.indexOf(child) == -1) {
                    // add element into queue
                    queue.add(child);
                    // make visited
                    visited.add(child);
                }
            }
        }

    }

    /**
     * @Desc: used for add Edges
     * @param u
     * @param v
     */
    private static void addEdge(ArrayList<ArrayList<Integer>> g,
             int u, int v) {
        // undirected graph
        g.get(u).add(v);
        g.get(v).add(u);
    }
}
//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges

C++

#include <bits/stdc++.h>
using namespace std;
//adjacency list
vector<int> adj[1001];
//visited array to hold
//which node is visit and which
//is not
bool visited[100001];
//function to add the edge
//into the adjacency list
void addEdge(int u,int v)
{
    //undirected graph
    adj[u].push_back(v);
    adj[v].push_back(u);
}
void bfsTraversal(int node)
{
    //queue to hold the nodes
    queue<int> q;
    q.push(node);
    //make visited the current node
    visited[node]=1;
    //iterate till queue is not empty
    while(!q.empty())
      {
          //store the front element from queue
          node=q.front();
          //print the front element of the queue
          cout<<node<<" ";
          //pop out the first element of the queue
          q.pop();
          //iterate through the adjacency list
          //of the popped element
          for(int child:adj[node])
            {
                //if not visited then push into
                //queue and make it as visited
                if(visited[child]==0)
                 {
                     q.push(child);
                     visited[child]=1;
                     
                 }
            }
      }
}
int main()
{
    int n=8;
    int edges=5;
    addEdge(1,2);
    addEdge(1,3);
    addEdge(4,5);
    addEdge(4,6);
    addEdge(7,8);
    cout<<"Connected Components are\n";
    for(int i=1;i<=n;i++)
      {
          if(visited[i]==0)
            {
                bfsTraversal(i);
                cout<<"\n";
            }
      }
    return 0;
}
//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges