Counting connected components in a graph

               It is a basic problem in graph. A graph contains nodes and edges. Nodes can be a vertices and edges connecting the nodes.

Here, connected component means every node is reached from any other node. The traversal of node may be DFS(Depth First Search) or BFS(Breadth First Search) according to it.

Let us count the counted component in graph.

Program implementation:

• This program gets the number of nodes and edges as input.
• It uses DFS(Depth first Search) to traverse the nodes. ‘g_dfs()’ used to traverse the graph.
• It gets the nodes, adjacent list and a Boolean value ‘g_visited’ to perform the traversal.
• It sets the ‘g_visited’ value when it reaches the node.
• ‘countIt()’ -This function gets the number of nodes and edges as input.
• It checks the ‘g_visited’  value for entire graph. Find the edges visited. Finally, gives you the count.
• ‘main()’ – this function assigns the input value as number of nodes and edges. It calls the countIt() function to get the counting value.  

Program:

import java.util.*;

public class CCCGEg {

    private static void g_dfs(int g_node, List<List<Integer>> g_adjList, boolean[] g_visited) {

        g_visited[g_node] = true;

        for (int neighbor : g_adjList.get(g_node)) {

            if (!g_visited[neighbor]) {

                g_dfs(neighbor, g_adjList, g_visited);

            }

        }

    }

    public static int countIt(int n, int[][] edges) {

        List<List<Integer>> g_adjList = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            g_adjList.add(new ArrayList<>());

        }

        for (int[] edge : edges) {

            g_adjList.get(edge[0]).add(edge[1]);

            g_adjList.get(edge[1]).add(edge[0]);

        }

        boolean[] g_visited = new boolean[n];

        int count = 0;

        for (int i = 0; i < n; i++) {

            if (!g_visited[i]) {

                g_dfs(i, g_adjList, g_visited);

                count++;

            }

        }

        return count;

    }

    public static void main(String[] args) {

        int n = 4;

        int[][] edges = {{0, 2},{2, 3}, {3,1}};

        System.out.println("The Count of connected components are: " + countIt(n, edges));

    }

}

Output:

C:\raji\blog>javac CCCGEg.java

C:\raji\blog>java CCCGEg

The Count of connected components are: 1

This is the way of creating the java program to count the connected components in a graph was done. Hope, this code gives you clear understanding to you. Keep coding!!!