2

我无法将快速查找算法中的联合操作与集合论中 AUB 的一般含义相关联。

书（C++ 中的算法 Robert Sedgewick）告诉联合操作是“扫描每个输入对的整个数组。（代码中的第 9 行和第 10 行）。

基本上，我们将节点 q 的值复制到与节点 p 具有相同值的所有其他节点。为什么我们将这个操作命名为 UNION？

代码直接从书中复制。

#include <iostream>
const int N = 10000;
int main() {
int i, p, q, id[N];
for( i = 0; i < N; i++ ) id[i] = i;
while( cin >> p >> q ) {
    int t = id[p];
    if ( t = id[q] ) continue;              //quick find operation
    for ( i = 0; i < N; i++ )               //---> union why?
        if ( id[i] == t) id[i] = id[q];
    cout << " " << p << " " << q << endl;
}
}
4

2 回答 2

2

快速查找中的联合步骤意味着合并具有相同 id 的组件。在一般意义上，它有点像两个集合的并集。您可以考虑两个集合，onw 将 id1 作为其所有组件的 id，另一个作为 id2。要获得很好的解释，请查看快速查找部分中的此演示文稿：

http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

于 2012-02-10T15:44:04.790 回答
1

查看支持的操作集。如果没有办法问“列出所有元素”，而只是插入、查找和联合，那么使用这些操作就无法判断是否存在重复元素。它使支持的操作更加高效，并且仍然像集合一样（据用户所知）。

于 2012-02-10T15:40:12.607 回答