Union-Find 并查集算法详细解释

文章结构概述

• 引言

  • 动态连通性

  • Union-Find

  • 算法实现与复杂度分析

  • • 快速查找
    • 快速联合
    • 带权重的快速联合
    • 带路径压缩的带权重快速联合
    • 算法复杂度分析

  • Python 全面实现带路径压缩的带权重快速联合算法

  • 参考资料

引言

领导 （面带笑容地走过来）：有一个具有挑战性但十分有趣的项目，你有没有兴趣尝试一下？
小溪子：（略显紧张）好的，非常愿意参与。
领导 ：目前一部手机通常会拥有多个名称，我们已经掌握了一些名称对应同一款手机的信息，现在需要设计一种算法，能够将同一部手机的所有名称整合为一个集合，使得给定任意一个名称都可以查询到其所属的集合，并判断两个名称是否等价（即是否属于同一款手机）。
小溪子：（恰好看到相关算法）这似乎属于动态连通性问题。

动态连通性分析

已知以下手机名称中，(0,1)、(0,2)、(0,3)、(3,4)、(5,6)以及(5,7)所对应的设备为同一款手机。