disjoint-sets - union find set 算法 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]);的意义和目的是什么？通常返回的是整数、布尔值或其他数据类型。

Answer 1

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

如《算法简介》（Cormen，第 571-572 页）第 3 版一书中所述：

单独地，按等级联合会产生O(m log n)的运行时间，而且这个界限很紧。虽然我们不会在这里证明它，但对于一系列 n 个 MAKE-SET 操作（因此最多n - 1 个UNION 操作）和 f 个 FIND-SET 操作，单独的路径压缩启发式给出了O的最坏情况运行时间(n + f * (1 + log _{2 + f/n} n))。

当我们同时使用按秩联合和路径压缩时，最坏情况的运行时间是O(m α(n))，其中α(n)是一个增长非常缓慢的函数，我们在第 21.4 节中对其进行了定义。在不相交集数据结构的任何可能的应用中， α(n) ≤ 4；因此，在所有实际情况下，我们可以将运行时间视为以m为单位的线性。然而，严格来说，它是超线性的。

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