Disjoint Set

释义 Definition

不相交集合（族）：指一组集合，它们两两之间没有共同元素。在计算机科学中常特指用于维护“元素分组/连通性”的数据结构与问题模型（也称 Union-Find / 并查集），支持高效的合并（union）与查找所属集合（find）操作。

发音 Pronunciation (IPA)

/dsdnt st/

例句 Examples

A and B are disjoint sets because they share no elements.
集合 A 和集合 B 是不相交集合，因为它们没有任何共同元素。

The algorithm uses a disjoint set to track connectivity as edges are added to the graph.
该算法使用并查集（不相交集合结构）在向图中不断添加边时跟踪连通性。

词源 Etymology

disjoint 来自前缀 dis-（表示“分开、否定”）+ joint（“连接的、关节/接合处”），字面意思是“不连接的”。set 表示“集合”，源自法语 set（与“放置、设定”相关的词源）。合起来 disjoint set 即“互不相交的集合”，在数学与计算机科学语境中被固定化使用。

文学与经典著作 Literary Works

Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein；常称 CLRS）在数据结构章节中讲解 disjoint-set data structure。
The Art of Computer Programming, Volume 1: Fundamental Algorithms（Donald E. Knuth）涉及集合、等价类与相关算法思想（与不相交集合/等价类划分紧密相关）。
Algorithms（Robert Sedgewick & Kevin Wayne）在图算法与动态连通性问题中使用并讲解 Union-Find / disjoint set。