介绍

连通元件

在图论中，元件又称为连通元件、元件、或分支，是一个无向子图，在元件中的任何两个顶点都可以经由该图上的边抵达另一个顶点，且没有任何一边可以连到其他子图的顶点。例如右图中的无向图可以分成 3 个无向子图，也就是 3 个元件。没有与任何其他顶点相连的单一顶点也可以算是一个元件。

如果图是一个有向图，而每 2 个顶点都存在可以来回该顶点的路径则称为强连通元件；而若图上任两个点之间皆有不止一条路径连通，则称为双连通元件（英语：Biconnected component）。

原理

使用 DFS 的无向图的连接元件

为无向图寻找连接原件是一项比较容易的任务。我们的想法是：从每个未访问的顶点开始做 BFS 或 DFS，我们得到所有强连接的组件。

按照下面提到的步骤，用 DFS 实现这个想法：

• 将所有顶点初始化为未访问的顶点。
• 对每个顶点做如下处理：
  • 如果 v 以前没有被访问过，则调用 DFS 进行访问
  • 将 v 标记为已访问。
  • 对于 v 的每一个相邻的 u，如果 u 未被访问，则递归调用 DFS。

使用 Disjoint Set Union 解决无向图的连接元件

使用 DSU (Disjoint Set Union) 来解决问题的想法是：最初将所有的节点声明为单独的子集（subsets），然后访问它们。当遇到一个新的未访问的节点时，将其与下面的节点联合（unite）起来。通过这种方式，在每次遍历中都会访问一个元件（component）。

按照下面的步骤来实现这个想法：

• 声明一个大小为 V 的数组 arr []，其中 V 是节点的总数。
• 对于数组 arr [] 的每个索引 i，其值表示第 i 个顶点的父节点是谁。
• 将每个节点初始化为自己的父节点，然后在将它们加在一起时，相应地改变它们的父节点。
• 遍历从 0 到 V 的节点：
  • 对于每个是自己的父节点，启动 DSU。
  • 打印该不相交集的节点，因为它们属于一个组件。

参考：

• 并查集 - Wikiwand (opens new window)

实现

使用 DFS:

JavaScript

class GraphUnweightedUndirectedAdjacencyList {
  // Unweighted Undirected Graph class
  constructor () {
    this.connections = {}
  }

  addNode (node) {
    // Function to add a node to the graph (connection represented by set)
    this.connections[node] = new Set()
  }

  addEdge (node1, node2) {
    // Function to add an edge (adds the node too if they are not present in the graph)
    if (!(node1 in this.connections)) { this.addNode(node1) }
    if (!(node2 in this.connections)) { this.addNode(node2) }
    this.connections[node1].add(node2)
    this.connections[node2].add(node1)
  }

  DFSComponent (components, node, visited) {
    // Helper function to populate the visited set with the nodes in each component

    // adding the first visited node in the component to the array
    components.push(node)
    const stack = [node]
    // populating the visited set using DFS (Iterative)
    while (stack.length > 0) {
      const curr = stack.pop()
      visited.add(curr.toString())
      for (const neighbour of this.connections[curr].keys()) {
        if (!visited.has(neighbour.toString())) { stack.push(neighbour) }
      }
    }
  }

  connectedComponents () {
    // Function to generate the Connected Components
    // Result is an array containing 1 node from each component
    const visited = new Set()
    const components = []
    for (const node of Object.keys(this.connections)) {
      if (!visited.has(node.toString())) { this.DFSComponent(components, node, visited) }
    }
    return components
  }
}

使用 DSU:

#include <bits/stdc++.h>
using namespace std;

int merge(int* parent, int x)
{
 if (parent[x] == x)
  return x;
 return merge(parent, parent[x]);
}

int connectedcomponents(int n, vector<vector<int> >& edges)
{
 int parent[n];
 for (int i = 0; i < n; i++) {
  parent[i] = i;
 }
 for (auto x : edges) {
  parent[merge(parent, x[0])] = merge(parent, x[1]);
 }
 int ans = 0;
 for (int i = 0; i < n; i++) {
  ans += (parent[i] == i);
 }
 for (int i = 0; i < n; i++) {
  parent[i] = merge(parent, parent[i]);
 }
 map<int, list<int> > m;
 for (int i = 0; i < n; i++) {
  m[parent[i]].push_back(i);
 }
 for (auto it = m.begin(); it != m.end(); it++) {
  list<int> l = it->second;
  for (auto x : l) {
   cout << x << " ";
  }
  cout << endl;
 }
 return ans;
}

int main()
{
 int n = 5;
 vector<int> e1 = { 0, 1 };
 vector<int> e2 = { 2, 1 };
 vector<int> e3 = { 3, 4 };
 vector<vector<int> > e;
 e.push_back(e1);
 e.push_back(e2);
 e.push_back(e3);

 cout << "Following are connected components:\n";
 int a = connectedcomponents(n, e);
 return 0;
}

扩展

• OpenCV Connected Component Labeling and Analysis - PyImageSearch (opens new window)

参考

• Component (graph theory) - Wikiwand (opens new window)
• 元件 (圖論) - Wikiwand (opens new window)
• Connected Components in an Undirected Graph - GeeksforGeeks (opens new window)
• Connected Component Visualization (opens new window)