Group Connected Components in an UnDirected Graph

In graph theory, a connected component refers to a subset of vertices in a graph where each vertex is connected to every other vertex in the subset, either directly or indirectly. Grouping all connected components in a graph is the process of identifying these subsets and assigning a unique identifier or label to each subset/group of vertices.

Labeling Connected Components Using Depth-First Search (DFS):

Depth-First Search (DFS) is a graph traversal algorithm that can be used to identify and label connected components in a graph. The process of using DFS for this purpose can be summarized as follows:

Start by iterating through all the nodes in the graph.
For each unvisited node, begin a DFS traversal starting from that node.
As the DFS traversal progresses, assign a unique identifier (e.g., a number) to all the nodes that are directly or indirectly connected to the starting node.
Repeat steps 2 and 3 for all the unvisited nodes in the graph.

By the end of this process, all the nodes in the graph will be assigned a unique identifier, and each set of connected nodes will have the same identifier. This effectively groups and labels the connected components in the graph.

Below is the implementation to find and label connected components in a given un-directed graph using Depth First Search:


# Function to label all connected nodes with a component ID using DFS
def label_nodes_dfs(current_node, component_id, graph, node_to_component_id):
  # Mark the current node as visited by assigning the component ID
  node_to_component_id[current_node] = component_id
  
  # Traverse all the neighbors of the current node
  for neighbor in graph[current_node]:
    # If the neighbor is not yet visited, recursively call the function
    if neighbor not in node_to_component_id:
      label_nodes_dfs(neighbor, component_id, graph, node_to_component_id)

# Function to find all connected components in the graph
def find_connected_components(graph):
  # Initialize the node to component ID mapping
  node_to_component_id = {}
  
  # Initialize the component ID
  component_id = 0
  
  # Iterate through all the nodes in the graph
  for node in graph:
    # If the node is not yet visited, start a new DFS traversal
    if node not in node_to_component_id:
      label_nodes_dfs(node, component_id, graph, node_to_component_id)
      component_id += 1
  
  return node_to_component_id

# Initialize a sample graph as an adjacency list
graph = {
  'A' : ['B', 'C'],
  'B' : ['A', 'C'],
  'C' : ['A', 'B'],
  'D' : ['E'],
  'E' : ['D'],
  'F' : []
}

node_to_component_id = find_connected_components(graph)
print("Below is the component ID given to each node:")
print(node_to_component_id)

# You can also group components based on ID and store them together
nodes_by_component_id = {}
for node,component_id in node_to_component_id.items():
  if component_id not in nodes_by_component_id:
    nodes_by_component_id[component_id] = []
  nodes_by_component_id[component_id].append(node)
print("Below are all the nodes in graph grouped by component ID:")
print(nodes_by_component_id)


#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

// Function to label all connected nodes with a component ID using DFS
void label_nodes_dfs(string current_node, int component_id, unordered_map<string, vector<string>>& graph, unordered_map<string, int>& node_to_component_id) {
  // Mark the current node as visited by assigning the component ID
  node_to_component_id[current_node] = component_id;

  // Traverse all the neighbors of the current node
  for (const string& neighbor : graph[current_node]) {
    // If the neighbor is not yet visited, recursively call the function
    if (node_to_component_id.find(neighbor) == node_to_component_id.end()) {
      label_nodes_dfs(neighbor, component_id, graph, node_to_component_id);
    }
  }
}

// Function to find all connected components in the graph
unordered_map<string, int> find_connected_components(unordered_map<string, vector<string>>& graph) {
  // Initialize the node to component ID mapping
  unordered_map<string, int> node_to_component_id;

  // Initialize the component ID
  int component_id = 0;

  // Iterate through all the nodes in the graph
  for (const auto& node_pair : graph) {
    const string& node = node_pair.first;
    // If the node is not yet visited, start a new DFS traversal
    if (node_to_component_id.find(node) == node_to_component_id.end()) {
      label_nodes_dfs(node, component_id, graph, node_to_component_id);
      component_id++;
    }
  }

  return node_to_component_id;
}

int main() {
  // Initialize a sample graph as an adjacency list
  unordered_map<string, vector<string>> graph = {
    {"A", {"B", "C"}},
    {"B", {"A", "C"}},
    {"C", {"A", "B"}},
    {"D", {"E"}},
    {"E", {"D"}},
    {"F", {}}
  };

  unordered_map<string, int> node_to_component_id = find_connected_components(graph);

  cout << "Below is the component ID given to each node:" << endl;
  for (const auto& pair : node_to_component_id) {
    cout << pair.first << ": " << pair.second << endl;
  }

  // Group components based on ID and store them together
  unordered_map<int, vector<string>> nodes_by_component_id;
  for (const auto& pair : node_to_component_id) {
    int component_id = pair.second;
    const string& node = pair.first;
    nodes_by_component_id[component_id].push_back(node);
  }

  cout << "Below are all the nodes in graph grouped by component ID:" << endl;
  for (const auto& pair : nodes_by_component_id) {
    int component_id = pair.first;
    const vector<string>& nodes = pair.second;
    cout << "Component " << component_id << ": ";
    for (const string& node : nodes) {
      cout << node << " ";
    }
    cout << endl;
  }

  return 0;
}


// Function to label all connected nodes with a component ID using DFS
function labelNodesDFS(currentNode, componentID, graph, nodeToComponentID) {
  // Mark the current node as visited by assigning the component ID
  nodeToComponentID[currentNode] = componentID;

  // Traverse all the neighbors of the current node
  for (let neighbor of graph[currentNode]) {
    // If the neighbor is not yet visited, recursively call the function
    if (!(neighbor in nodeToComponentID)) {
      labelNodesDFS(neighbor, componentID, graph, nodeToComponentID);
    }
  }
}

// Function to find all connected components in the graph
function findConnectedComponents(graph) {
  // Initialize the node to component ID mapping
  let nodeToComponentID = {};

  // Initialize the component ID
  let componentID = 0;

  // Iterate through all the nodes in the graph
  for (let node in graph) {
    // If the node is not yet visited, start a new DFS traversal
    if (!(node in nodeToComponentID)) {
      labelNodesDFS(node, componentID, graph, nodeToComponentID);
      componentID += 1;
    }
  }

  return nodeToComponentID;
}

// Initialize a sample graph as an adjacency list
let graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C'],
  'C': ['A', 'B'],
  'D': ['E'],
  'E': ['D'],
  'F': []
};

let nodeToComponentID = findConnectedComponents(graph);
console.log("Below is the component ID given to each node:");
console.log(nodeToComponentID);

// You can also group components based on ID and store them together
let nodesByComponentID = {};
for (let node in nodeToComponentID) {
  let componentID = nodeToComponentID[node];
  if (!(componentID in nodesByComponentID)) {
    nodesByComponentID[componentID] = [];
  }
  nodesByComponentID[componentID].push(node);
}
console.log("Below are all the nodes in graph grouped by component ID:");
console.log(nodesByComponentID);


import java.util.HashMap;
import java.util.Map;

public class Main {

  // Function to label all connected nodes with a component ID using DFS
  private static void labelNodesDFS(String currentNode, int componentId, Map<String, Map<String, Boolean>> graph, Map<String, Integer> nodeToComponentId) {
    // Mark the current node as visited by assigning the component ID
    nodeToComponentId.put(currentNode, componentId);

    // Traverse all the neighbors of the current node
    for (String neighbor : graph.get(currentNode).keySet()) {
      // If the neighbor is not yet visited, recursively call the function
      if (!nodeToComponentId.containsKey(neighbor)) {
        labelNodesDFS(neighbor, componentId, graph, nodeToComponentId);
      }
    }
  }

  // Function to find all connected components in the graph
  private static Map<String, Integer> findConnectedComponents(Map<String, Map<String, Boolean>> graph) {
    // Initialize the node to component ID mapping
    Map<String, Integer> nodeToComponentId = new HashMap<>();

    // Initialize the component ID
    int componentId = 0;

    // Iterate through all the nodes in the graph
    for (String node : graph.keySet()) {
      // If the node is not yet visited, start a new DFS traversal
      if (!nodeToComponentId.containsKey(node)) {
        labelNodesDFS(node, componentId, graph, nodeToComponentId);
        componentId++;
      }
    }

    return nodeToComponentId;
  }

  public static void main(String[] args) {
    // Initialize a sample graph as an adjacency list
    Map<String, Map<String, Boolean>> graph = new HashMap<>();
    graph.put("A", new HashMap<>() {{ put("B", true); put("C", true); }});
    graph.put("B", new HashMap<>() {{ put("A", true); put("C", true); }});
    graph.put("C", new HashMap<>() {{ put("A", true); put("B", true); }});
    graph.put("D", new HashMap<>() {{ put("E", true); }});
    graph.put("E", new HashMap<>() {{ put("D", true); }});
    graph.put("F", new HashMap<>());

    Map<String, Integer> nodeToComponentId = findConnectedComponents(graph);
    System.out.println("Below is the component ID given to each node:");
    System.out.println(nodeToComponentId);

    // Group components based on ID and store them together
    Map<Integer, java.util.List<String>> nodesByComponentId = new HashMap<>();
    for (Map.Entry<String, Integer> entry : nodeToComponentId.entrySet()) {
      int componentId = entry.getValue();
      if (!nodesByComponentId.containsKey(componentId)) {
        nodesByComponentId.put(componentId, new java.util.ArrayList<>());
      }
      nodesByComponentId.get(componentId).add(entry.getKey());
    }
    System.out.println("Below are all the nodes in graph grouped by component ID:");
    System.out.println(nodesByComponentId);
  }
}

Labeling Connected Components Using Breadth-First Search (BFS):

Breadth-First Search (BFS) technique can also be used to group connected components. The BFS approach explores all the neighboring vertices at the current depth before moving on to the vertices at the next depth level. Below is the implementation of this approach:


from collections import deque

# Function to label all connected nodes with a component ID using BFS
def label_nodes_bfs(start_node, component_id, graph, node_to_component_id):
  # Initialize a queue for BFS
  queue = deque([start_node])
  
  # Mark the start node as visited by assigning the component ID
  node_to_component_id[start_node] = component_id
  
  while queue:
    current_node = queue.popleft()
    
    # Traverse all the neighbors of the current node
    for neighbor in graph[current_node]:
      # If the neighbor is not yet visited, mark it and add it to the queue
      if neighbor not in node_to_component_id:
        node_to_component_id[neighbor] = component_id
        queue.append(neighbor)

# Function to find all connected components in the graph
def find_connected_components(graph):
  # Initialize the node to component ID mapping
  node_to_component_id = {}
  
  # Initialize the component ID
  component_id = 0
  
  # Iterate through all the nodes in the graph
  for node in graph:
    # If the node is not yet visited, start a new BFS traversal
    if node not in node_to_component_id:
      label_nodes_bfs(node, component_id, graph, node_to_component_id)
      component_id += 1
  
  return node_to_component_id

# Initialize a sample graph as an adjacency list
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C'],
  'C': ['A', 'B'],
  'D': ['E'],
  'E': ['D'],
  'F': []
}

node_to_component_id = find_connected_components(graph)
print("Below is the component ID given to each node:")
print(node_to_component_id)

# Group components based on ID and store them together
nodes_by_component_id = {}
for node, component_id in node_to_component_id.items():
  if component_id not in nodes_by_component_id:
    nodes_by_component_id[component_id] = []
  nodes_by_component_id[component_id].append(node)

print("Below are all the nodes in graph grouped by component ID:")
print(nodes_by_component_id)


#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>

// Function to label all connected nodes with a component ID using BFS
void label_nodes_bfs(std::string start_node, int component_id, std::unordered_map<std::string, std::vector<std::string>>& graph, std::unordered_map<std::string, int>& node_to_component_id) {
  // Initialize a queue for BFS
  std::queue<std::string> queue;
  queue.push(start_node);

  // Mark the start node as visited by assigning the component ID
  node_to_component_id[start_node] = component_id;

  while (!queue.empty()) {
    std::string current_node = queue.front();
    queue.pop();

    // Traverse all the neighbors of the current node
    for (const auto& neighbor : graph[current_node]) {
      // If the neighbor is not yet visited, mark it and add it to the queue
      if (node_to_component_id.find(neighbor) == node_to_component_id.end()) {
        node_to_component_id[neighbor] = component_id;
        queue.push(neighbor);
      }
    }
  }
}

// Function to find all connected components in the graph
std::unordered_map<std::string, int> find_connected_components(std::unordered_map<std::string, std::vector<std::string>>& graph) {
  // Initialize the node to component ID mapping
  std::unordered_map<std::string, int> node_to_component_id;

  // Initialize the component ID
  int component_id = 0;

  // Iterate through all the nodes in the graph
  for (const auto& node : graph) {
    // If the node is not yet visited, start a new BFS traversal
    if (node_to_component_id.find(node.first) == node_to_component_id.end()) {
      label_nodes_bfs(node.first, component_id, graph, node_to_component_id);
      component_id++;
    }
  }

  return node_to_component_id;
}

int main() {
  // Initialize a sample graph as an adjacency list
  std::unordered_map<std::string, std::vector<std::string>> graph = {
    {"A", {"B", "C"}},
    {"B", {"A", "C"}},
    {"C", {"A", "B"}},
    {"D", {"E"}},
    {"E", {"D"}},
    {"F", {}}
  };

  std::unordered_map<std::string, int> node_to_component_id = find_connected_components(graph);

  std::cout << "Below is the component ID given to each node:" << std::endl;
  for (const auto& pair : node_to_component_id) {
    std::cout << pair.first << ": " << pair.second << std::endl;
  }

  // Group components based on ID and store them together
  std::unordered_map<int, std::vector<std::string>> nodes_by_component_id;
  for (const auto& pair : node_to_component_id) {
    if (nodes_by_component_id.find(pair.second) == nodes_by_component_id.end()) {
      nodes_by_component_id[pair.second] = std::vector<std::string>();
    }
    nodes_by_component_id[pair.second].push_back(pair.first);
  }

  std::cout << "Below are all the nodes in graph grouped by component ID:" << std::endl;
  for (const auto& pair : nodes_by_component_id) {
    std::cout << "Component ID " << pair.first << ": ";
    for (const auto& node : pair.second) {
      std::cout << node << " ";
    }
    std::cout << std::endl;
  }

  return 0;
}


// Function to label all connected nodes with a component ID using BFS
function labelNodesBFS(startNode, componentID, graph, nodeToComponentID) {
  // Initialize a queue for BFS
  const queue = [startNode];

  // Mark the start node as visited by assigning the component ID
  nodeToComponentID[startNode] = componentID;

  while (queue.length > 0) {
    const currentNode = queue.shift();

    // Traverse all the neighbors of the current node
    for (const neighbor of graph[currentNode]) {
      // If the neighbor is not yet visited, mark it and add it to the queue
      if (!(neighbor in nodeToComponentID)) {
        nodeToComponentID[neighbor] = componentID;
        queue.push(neighbor);
      }
    }
  }
}

// Function to find all connected components in the graph
function findConnectedComponents(graph) {
  // Initialize the node to component ID mapping
  const nodeToComponentID = {};

  // Initialize the component ID
  let componentID = 0;

  // Iterate through all the nodes in the graph
  for (const node in graph) {
    // If the node is not yet visited, start a new BFS traversal
    if (!(node in nodeToComponentID)) {
      labelNodesBFS(node, componentID, graph, nodeToComponentID);
      componentID += 1;
    }
  }

  return nodeToComponentID;
}

// Initialize a sample graph as an adjacency list
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C'],
  'C': ['A', 'B'],
  'D': ['E'],
  'E': ['D'],
  'F': []
};

const nodeToComponentID = findConnectedComponents(graph);
console.log("Below is the component ID given to each node:");
console.log(nodeToComponentID);

// Group components based on ID and store them together
const nodesByComponentID = {};
for (const node in nodeToComponentID) {
  const componentID = nodeToComponentID[node];
  if (!(componentID in nodesByComponentID)) {
    nodesByComponentID[componentID] = [];
  }
  nodesByComponentID[componentID].push(node);
}

console.log("Below are all the nodes in graph grouped by component ID:");
console.log(nodesByComponentID);


import java.util.*;

public class Main {
  // Function to label all connected nodes with a component ID using BFS
  public static void labelNodesBFS(String startNode, int componentID, Map<String, List<String>> graph, Map<String, Integer> nodeToComponentID) {
    // Initialize a queue for BFS
    Deque<String> queue = new LinkedList<>();
    queue.offer(startNode);

    // Mark the start node as visited by assigning the component ID
    nodeToComponentID.put(startNode, componentID);

    while (!queue.isEmpty()) {
      String currentNode = queue.pollFirst();

      // Traverse all the neighbors of the current node
      for (String neighbor : graph.get(currentNode)) {
        // If the neighbor is not yet visited, mark it and add it to the queue
        if (!nodeToComponentID.containsKey(neighbor)) {
          nodeToComponentID.put(neighbor, componentID);
          queue.offer(neighbor);
        }
      }
    }
  }

  // Function to find all connected components in the graph
  public static Map<Integer, List<String>> findConnectedComponents(Map<String, List<String>> graph) {
    // Initialize the node to component ID mapping
    Map<String, Integer> nodeToComponentID = new HashMap<>();

    // Initialize the component ID
    int componentID = 0;

    // Iterate through all the nodes in the graph
    for (String node : graph.keySet()) {
      // If the node is not yet visited, start a new BFS traversal
      if (!nodeToComponentID.containsKey(node)) {
        labelNodesBFS(node, componentID, graph, nodeToComponentID);
        componentID++;
      }
    }

    // Group components based on ID and store them together
    Map<Integer, List<String>> nodesByComponentID = new HashMap<>();
    for (Map.Entry<String, Integer> entry : nodeToComponentID.entrySet()) {
      int id = entry.getValue();
      String node = entry.getKey();
      if (!nodesByComponentID.containsKey(id)) {
        nodesByComponentID.put(id, new ArrayList<>());
      }
      nodesByComponentID.get(id).add(node);
    }

    return nodesByComponentID;
  }

  public static void main(String[] args) {
    // Initialize a sample graph as an adjacency list
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("B", "C"));
    graph.put("B", Arrays.asList("A", "C"));
    graph.put("C", Arrays.asList("A", "B"));
    graph.put("D", Arrays.asList("E"));
    graph.put("E", Arrays.asList("D"));
    graph.put("F", new ArrayList<>());

    Map<Integer, List<String>> nodesByComponentID = findConnectedComponents(graph);
    System.out.println("Below is the component ID given to each node:");
    System.out.println(nodeToComponentID);

    System.out.println("Below are all the nodes in graph grouped by component ID:");
    System.out.println(nodesByComponentID);
  }
}

Applications of Grouping Connected Components:

Grouping connected components in a graph has various applications, such as:

Social network analysis: Identifying communities or clusters of users in a social network.
Recommendation systems: Grouping related items or products to provide better recommendations.
Image segmentation: Separating an image into distinct regions or objects.
Bioinformatics: Analyzing protein-protein interaction networks or gene regulatory networks.
Network routing and connectivity: Identifying independent network segments or subnetworks.