并查集算法 - Algorithms, Part I, week 1 UNION-FIND
前言 如果能够科学上网,英文水平良好,建议登入cousera进行学习。平台上有完整的作业提交平台,对提交的作业有详细的性能诊断和反馈;有课程各种资源;有课程讨论。在课程提问区提问还会收到导师的回答。链接:Algorithms, Part IAlgorithms, Part II 《算法》第四版:testbook链接(英文):在此 主要内容 并查集是一种树形的数据结构,通过这种数据结构能够有效处理不相交集合间的合并(union)及查询(find)问题。比如动态连通性问题。这种数据结构主要涉及两个操作: Find:查询元素属于哪一个子集。此操作还可以用来确定两个元素是否属于同一子集。 Union:将两个子集合并成到一个集合中。 1. 动态连通性问题(dynamic connectivity) 动态连通性的应用很广泛: 比如网络诊断:网络中的两台计算机是否连通,社交网络中的两个人是否存在交集,芯片中的电路元件连通性等等。场景:对象 数码照片:像素 网络:计算机 社交网络:人 ... 在编程中我们会对所有这些不同类型的对象进行简单的编号(0 -- N-1),这样方便利用整数作为数组的索引号,快...