UNION—FIND算法及其相关问题

UNION-FIND Algorithm and Related Problems

本文讨论了UNION—FIND算法已获得的主要理论分析结果,包括具有渐近最优特性的各种α算法(几乎线性算法)和不相交集合合并的特殊情形的线性算法及其相关问题。

This paper summarizes the main results obtained by theoretic analysis for Union-Find algorithm, including various α algorithms (almost linear algorithm) with asymptotic optimal performance, a lincar-time algorithm for a special case of disjoint set union and some related problems.