动态连通性问题

“连通” 是一种等价关系，两个对象 p 和 q 是相连通的，意味着它具有：

  • 自反性：p 和 p 是相连的
  • 对称性：如果 p 和 q 是相连的，那么 q 和 p 也是相连的
  • 传递性：如果 p 和 q 相连且 q 和 r 相连，那么 p 和 r 也是相连的

等价关系将对象分为多个等价类，在这个，当且仅当两个对象相连通时才属于同一个等价类。

使用一个数据结构保存 n 个对象的连通关系，并用来判断一对新的对象是否相连，这样的问题就是动态连通性问题，该数据结构叫做 并查集 。

在网络中等价类叫做连通分量。

并查集的操作

  • init(): 初始化所有对象
  • find(p): 返回 p 所在的连通分量
  • union(p, q): 在 p 和 q 直接添加一条连接
  • connected(p, q): 如果 p 和 q 在同一连通分量则返回 true
  • count(): 连通分量的数量

普通并查集

并查集使用数组保存每个对象的关系，对象 p 作为数组的索引，值为连通分量的 id 。

init 时每个对象都不连通，即连通分量 id 都为自身，cnt 记录连通分量数量

1
2
3
4
5
6

void init(vector<int>& uf) {
    for (int i = 0; i < uf.size(); i++) {
        uf[i] = i;
    }
    cnt = uf.size()
}

find 时直接返回对应的连通分量

1
2
3

int find(vector<int>& uf, int p) {
    return uf[p];
}

union 时如果 p 和 q 的连通分量不同，将 q 的连通分量下所有对象的连通分量 id 改为 p 的连通分量 id

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void un(vector<int>& uf, int p, int q) {
    int pId = find(p);
    int qId = find(q);
    if (pId == qId) {
        return;
    }
    for (int i = 0; i < uf.size(); i++) {
        if (uf[i] == qId) {
            uf[i] = pId;
        }
    }
    cnt--;
}

connected 只需判断 p 和 q 的连通分量 id 是否相同

1
2
3

bool connected(vector<int>& uf, int p, int q) {
    return find(p) == find(q);
}

count 时返回连通分量的计数

1
2
3

int count() {
    return cnt;
}

find-union 优化

对象 p 在数组中记录的值 uf[p] 指向同一连通分量的其它对象，根对象指向它自己。

因此 find 时需要一直查找到根对象

1
2
3
4
5
6

int find(vector<int>& uf, int p) {
    while (uf[p] != p) {
        p = uf[p];
    }
    return uf[p];
}

union 时只需要将 p 和 q 的根对象统一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void un(vector<int>& uf, int p, int q)
{
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot) {
        return;
    }
    uf[qRoot] = pRoot;
    cnt--;
}

这样处理后，这个 uf 的结构就是一个森林，每个连通分量就是森林里的一颗树

加权 union 算法

在 union 时将小的连通分量连接到大的连通分量上，减少树的深度，使用额外的数组记录连通分量节点数量，初始化时为 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void un(vector<int>& uf, vector<int>& w, int p, int q)
{
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot) {
        return;
    }
    if (w[pRoot] > w[qRoot]) {
        uf[qRoot] = pRoot;
        w[pRoot] += w[qRoot];
    } else {
        uf[pRoot] = qRoot;
        w[qRoot] += w[pRoot];
    }
    cnt--;
}

路径压缩的 find 算法

即将所有节点连接到根节点上，在 find 时实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int find(vector<int>& uf, int p)
{
    int pRoot = p;
    while (uf[pRoot] != pRoot) {
        pRoot = uf[pRoot];
    }
    // 路径压缩
    while (uf[p] != p) {
        p = uf[p];
        uf[p] = pRoot;
    }
    return p;
}

递归版本：

1
2
3
4
5
6
7
8

int find(vector<int>& uf, int p)
{
    if (uf[p] != p) {
        uf[p] = find(uf, uf[p]);
    }

    return uf[p];
}

实战

leetcode

1971: https://leetcode.cn/problems/find-if-path-exists-in-graph/description/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    int ufFind(vector<int>& uf, int p) {
        int start = p;
        while (uf[p] != p) {
            p = uf[p];
        }
        while (uf[start] != p) {
            start = uf[start];
            uf[start] = p;
        }
        return p;
    }

    void ufUnion(vector<int>& uf, int p, int q) {
        int pRoot = ufFind(uf, p);
        int qRoot = ufFind(uf, q);
        if (pRoot == qRoot) {
            return;
        }
        uf[pRoot] = qRoot;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> uf(n);
        for (int i = 0; i < n; i++) {
            uf[i] = i;
        }
        for (const auto& edge: edges) {
            ufUnion(uf, edge[0], edge[1]);
        }
        return ufFind(uf, source) == ufFind(uf, destination);
    }
};