Disjoint-set

释义 Definition

disjoint-set（不相交集合 / 并查集）：一种在计算机科学中常用的数据结构，用来维护若干个互不重叠（不相交）的集合，并高效支持两类操作：判断两个元素是否属于同一集合，以及将两个集合合并。（也常称 Union-Find。）

发音 Pronunciation (IPA)

/dɪsˈdʒɔɪnt sɛt/

例句 Examples

We use a disjoint-set to track which nodes are connected.
我们用并查集来跟踪哪些节点是连通的。

By applying path compression and union by rank, the disjoint-set supports near-constant-time connectivity queries in large graphs.
通过路径压缩和按秩合并，并查集在大型图中几乎能以常数时间回答连通性查询。

词源 Etymology

disjoint 来自拉丁语系词根，含义是“分开、互不相交”；set 源自数学语境中的“集合”。合起来 disjoint-set 字面意思就是“互不相交的集合”，用于描述一组彼此没有交集的集合族。在算法教材中，这个结构因其核心操作 union（合并） 与 find（查找/判定归属），也常被称为 union-find。

相关词 Related Words

• Disjoint
• Set
• Union-Find
• Union
• Find
• Partition
• Connectivity
• Graph
• Kruskal

文学与著作 Literary Works

• **Thomas H. Cormen et al.**，《Introduction to Algorithms（算法导论）》：在“Disjoint Sets / Union-Find”相关章节系统介绍并查集及其优化（路径压缩、按秩合并）。
• Robert Sedgewick & Kevin Wayne，《Algorithms》：在动态图连通性、最小生成树等主题中使用并查集作为核心工具。
• Robert E. Tarjan 的经典论文（如 1970s 相关工作）：奠定并查集高效实现与复杂度分析的理论基础，推动其成为算法中的标准结构。