并查集（Disjoin-Set）简介

  • 并查集（不相交集合）用于处理 动态连通性 问题，最典型的应用是求解【最小生成树】的 Kruskal 算法；
  • 并查集支持【查询（find）】、【合并（union）】两个操作；
  • 并查集只回答两个结点是不是在一个连通分量中（也就是所谓的连通性问题），并不回答路径问题；
  • 如果一个问题具有传递性质，可以考虑用并查集；
  • 并查集最常见的一种设计思想是：把同在一个连通分量中的结点组织成一个树形结构（代表元法）；
  • 并查集使用【路径压缩】与【按秩合并】解决树的高度增加带来的【查询】性能消耗问题；