union find set algorithm return parent[v] = find_set(parent[v]);方法

Question

int find_set(int v) {
if (v == parent[v])
    return v;
return parent[v] = find_set(parent[v]); }

这是disjoin set算法的一段代码请问return parent[v] = find_set(parent[v]); 的含义和目的是什么？通常 return 是整数、布尔值或其他数据类型。

Answer 1

那行代码 (parent[v] = find_set(parent[v]);) 是一种启发式优化，称为 路径压缩，一种简单而高效的启发式优化。路径压缩使得 find_set 路径上的每个节点都直接指向根。在之前路径中的任何节点上进一步调用 find_set 将非常快。此启发式的时间复杂度如下所示。

如《算法导论》（Cormen，第 571-572 页），第 3 版所述：

Alone, union by rank yields a running time of O(m log n), and this bound is tight. Although we shall not prove it here, for a sequence of n MAKE-SET operations (and hence at most n - 1 UNION operations) and f FIND-SET operations, the path-compression heuristic alone gives a worst-case running time of O(n + f * (1 + log_{2 + f/n}n)).

When we use both union by rank and path compression, the worst-case running time is O(m α(n)), where α(n) is a very slowly growing function, which we define in Section 21.4. In any conceivable application of a disjoint-set data structure, α(n) ≤ 4; thus, we can view the running time as linear in m in all practical situations. Strictly speaking, however, it is superlinear.

你可以通过阅读那本书了解更多。

union find set algorithm return parent[v] = find_set(parent[v]);方法

union find set algorithm return parent[v] = find_set(parent[v]); means

disjoint-sets

disjoint-union