边的顺序在 union find 中重要吗？

Question

我正在学习union-find and to understand it better, I have written a small程序：

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
 
vector<int> parent, sz;
 
int find(int i) {
    if(parent[i]==i) return i;
    return parent[i]=find(parent[i]);
}
 
void merge(int i, int j) {
    int p1=find(i);
    int p2=find(j);
 
    if(p1==p2) return;
    if(sz[p1]<sz[p2]) {
        parent[p1]=p2;
        sz[p2]+=sz[p1];
    } else {
        parent[p2]=p1;
        sz[p1]+=sz[p2];
    }
}
 
int main() {
    vector<vector<int>> allowedSwaps={{0,4},{4,2},{1,3},{1,4}};
 
    int n=5;    //hard-code for now
    sz.resize(n,1);
    parent.resize(n);
    iota(begin(parent),end(parent),0);
 
    cout<<"Parents before: \n";
    for(auto& e: parent)
        cout<<e<<" ";
    cout<<"\n";
 
    for(vector<int>& currswap: allowedSwaps) {
        merge(currswap[0],currswap[1]);
    }
 
    cout<<"Parents after: \n";
    for(auto& e: parent)
        cout<<e<<" ";
    cout<<"\n";
 
    return 0;
}

allowedSwaps 本质上表示所有相互连接的组件。对于上面的代码，它们都是连接的。

但是，如果您注意到输出：

Parents before: 
0 1 2 3 4 
Parents after: 
0 0 0 1 0

说明其中一个（3，0-indexed）没有连接。我认为那是因为当我们处理边 {1,3} 时，顶点 1 和 3 都还没有连接到更大的组件（它们稍后由 {1,4} ) 因此 Union Find 确定它是一个不同的组件。

这是否意味着边的顺序对于联合查找很重要？或者，我错过了什么吗？

Answer 1

您得到的输出并不表示有一个节点断开。

parent 数据结构表示从一个节点到另一个节点（或它本身，当它是根时）的链接。

一开始你有这个：

最后我们有这个：

这里重要的是有一棵树。并不要求所有节点都直接链接到根，只需要它们有一条到根的路径，对于索引为3的节点也是如此。

注意：如果你调用 find(3)，那么索引 3 也会收到值 0。它只是通过调用 find 得到优化的东西，但它不会改变的含义结果。

Answer 2

到目前为止，我一直在回答你的问题：

Parents after:
0 0 0 1 0
It shows that one of them (3, 0-indexed) is not connected.

实际上，项目 3 确实链接到所有其他项目。想想如果你在这里调用 find(3) 会发生什么。由于 3 的父级为 1，而 1 的父级为 0，因此我们调用 find(3) 将 return 0，即包含其他所有内容的同一集群。

我认为这里可能会让您感到困惑的是，即使两个元素的直接父元素不同，它们也可以位于同一簇中。这很正常，这就是为什么 find 函数会跟踪父项，直到找到属于它自己的父项的项目。

Answer 3

您正在处理路径压缩问题。合并所有连接的组件后，只需为每个元素调用 find() 函数。请考虑在程序末尾添加以下行：

for(int i=0; i<5; i+=1) find(i);

cout<<"Parents after path compression: \n";
for(auto& e: parent)
    cout<<e<<" ";
cout<<"\n";

你会得到这样的预期结果：

Parents before: 
0 1 2 3 4 
Parents after: 
0 0 0 1 0 
Parents after path compression: 
0 0 0 0 0

边的顺序在 union find 中重要吗？

Do the order of edges matter in union find?

c++

algorithm

disjoint-sets

union-find