Union-Find の基本きほん

date2026-07-14document_iddoc_cd1649d271040841319f831533eb8352description素集合分割、find、unionを定義し、経路圧縮とランク併合を用いるUnion-Findの計算量を説明する。prerequisites木とヒープの基本 / グラフの基本 / 計算量の基本type講義statusactive

algorithmdata-structuresundergraduatelecture

data/lecture/information/algorithm/data-structures/tree-and-heap-basics.lecture.n.md data/lecture/information/graph/graph-basics.lecture.n.md

1導入どうにゅう

この講義こうぎでは、互たがいに素そな集合族しゅうごうぞくが定さだめる分割ぶんかつを定義ていぎし、find と union を提供ていきょうする Union-Find の表現ひょうげんおよび計算量けいさんりょうを説明せつめいする。

2素集合分割そしゅうごうぶんかつと操作そうさ

集合しゅうごう $U$ の分割ぶんかつpartitionとは、空くうでない部分集合族ぶぶんしゅうごうぞく $[PARSE ERROR: Undefined("Command(\"mathcal\")")] P$ であって、異ことなる二集合にしゅうごうが互たがいに素そであり、その和集合わしゅうごうが $U$ となるものである。Union-Find（disjoint-set union）は、この分割ぶんかつに対たいして次つぎの操作そうさを提供ていきょうする。

$find (x)$ は、 $x$ を含ふくむ集合しゅうごうに割わり当あてられた代表元だいひょうげんrepresentativeを返かえす。同一集合どういつしゅうごうの要素ようそは同一どういつの代表元だいひょうげんをもち、 $find (x) = find (y)$ と $x, y$ が同一集合どういつしゅうごうに属ぞくすることは同値どうちである。
$union (x, y)$ は、 $x$ と $y$ を含ふくむ二集合にしゅうごうを一集合いちしゅうごうへ併合へいごうする。既すでに同一集合どういつしゅうごうなら分割ぶんかつを変更へんこうしない。

初期状態しょきじょうたいでは、各要素かくようそが一要素集合いちようそしゅうごうを構成こうせいするものとする。Union-Find は集合しゅうごうの併合へいごうを処理しょりするが、集合しゅうごうの分割ぶんかつや要素ようその削除さくじょは標準操作ひょうじゅんそうさに含ふくまれない。

find と union の引数ひきすうは $U$ の要素ようそであることを事前条件じぜんじょうけんとする。 $U = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ の場合ばあい、初期分割しょきぶんかつは空族くうぞくであり、有効ゆうこうな find または union の呼出よびだしは存在そんざいしない。

3親おやの森もりによる表現ひょうげん

各集合かくしゅうごうを根付ねつき木ぎで表現ひょうげんし、全体ぜんたいを根付ねつき木ぎの森もりとして保持ほじする。各要素かくようそ $x$ は親おや $parent [x]$ をもち、根ね $r$ では $parent [r] = r$ とする。根ねがその集合しゅうごうの代表元だいひょうげんである。find は親おやを反復的はんぷくてきに参照さんしょうして根ねへ到達とうたつし、union は二ふたつの根ねの一方いっぽうを他方たほうの子こにする。

3.1経路圧縮けいろあっしゅく

find の実行中じっこうちゅうに参照さんしょうした各頂点かくちょうてんの親おやを根ねへ変更へんこうする方法ほうほうを経路圧縮けいろあっしゅくpath compressionという。分割ぶんかつと代表元だいひょうげんを変更へんこうせず、後続こうぞくする find の親参照回数おやさんしょうかいすうを削減さくげんする。

3.2ランクによる併合へいごう

根ねに木きの高たかさの上界じょうかいを表あらわすランクrankを保持ほじし、union で小ちいさいランクの根ねを大おおきいランクの根ねの子こにする。同一どういつのランクなら一方いっぽうを子こにし、新あたらしい根ねのランクを $1$ 増加ぞうかさせる。経路圧縮後けいろあっしゅくごのランクは実際じっさいの高たかさと一致いっちするとは限かぎらないが、併合規則へいごうきそくに使用しようできる。

4計算量けいさんりょうと適用範囲てきようはんい

配列要素はいれつようその参照さんしょうと更新こうしんを $O (1)$ とする計算模型けいさんもけいを仮定かていする。 $n$ 個この一要素集合いちようそしゅうごうの初期化しょきかと、経路圧縮けいろあっしゅくおよびランクによる併合へいごうを併用へいようした $m$ 回かいの find・union からなる操作列そうされつの総時間そうじかんには、標準的ひょうじゅんてきな簡略上界かんりゃくじょうかい $O ((n + m) α (n))$ を使用しようできる。ここで $α$ は逆ぎゃく Ackermann 関数かんすうである。より精密せいみつな表記ひょうきでは、その引数ひきすうを $n$ と $m$ の双方そうほうから定さだめる。この評価ひょうかは操作列全体そうされつぜんたいに対たいするならし計算量けいさんりょうamortized complexityであり、各操作かくそうさの最悪時間さいあくじかんが定数ていすうであることを意味いみしない。記憶領域きおくりょういきは $O (n)$ である。

無向むこうグラフへ辺へんを追加ついかする際さいに両端点りょうたんてんを union すれば、find の代表元だいひょうげんの比較ひかくによって連結性れんけつせいを管理かんりできる。ただし、Union-Find は連結経路れんけつけいろや最短路さいたんろを復元ふくげんせず、辺へんの削除さくじょを直接ちょくせつには処理しょりしない。

Union-Find Basics

data/lecture/information/algorithm/data-structures/tree-and-heap-basics.lecture.n.md data/lecture/information/graph/graph-basics.lecture.n.md

1Introduction

This lecture defines a partition into pairwise disjoint sets and explains the representation and complexity of Union-Find, which provides the find and union operations.

2Disjoint-set partitions and operations

A partition of a set $U$ is a family $[PARSE ERROR: Undefined("Command(\"mathcal\")")] P$ of nonempty subsets whose distinct members are pairwise disjoint and whose union is $U$ . Union-Find, also called disjoint-set union, supports the following operations on such a partition.

$find (x)$ returns the representative assigned to the set containing $x$ . Elements in one set have the same representative, so $find (x) = find (y)$ if and only if $x$ and $y$ belong to the same set.
$union (x, y)$ merges the sets containing $x$ and $y$ . It leaves the partition unchanged if they are already the same set.

Initially, each element forms a singleton set. Union-Find supports merging sets; splitting a set and deleting an element are not standard operations.

Every argument to find or union must belong to $U$ . If $U = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ , the initial partition is the empty family and there is no valid call to find or union.

3Parent-forest representation

Represent each set by a rooted tree and store the collection as a forest of rooted trees. Every element $x$ has a parent $parent [x]$ , and a root $r$ satisfies $parent [r] = r$ . The root is the representative of its set. Find follows parent references to a root. Union makes one of two roots a child of the other.

3.1Path compression

Path compression changes the parent of every vertex visited by find to the root. It preserves the partition and representative while reducing the number of parent references in later find operations.

3.2Union by rank

Store at each root a rank that is an upper bound on tree height. Union makes the root of smaller rank a child of the root of larger rank. If their ranks are equal, it chooses either root as the child and increments the other root's rank. After path compression, rank need not equal actual height, but it remains suitable for the union rule.

4Complexity and scope

Assume that accessing or updating one array entry takes $O (1)$ time. Initializing $n$ singleton sets and then processing $m$ find and union operations with path compression and union by rank admits the standard simplified upper bound $O ((n + m) α (n))$ , where $α$ is the inverse Ackermann function. More precise notation defines its argument using both $n$ and $m$ . This is an amortized complexity bound over the whole sequence; it does not state that every operation has constant worst-case time. The structure uses $O (n)$ space.

When an edge is added to an undirected graph, unioning its endpoints permits connectivity queries by comparing representatives returned by find. Union-Find does not reconstruct a connecting path or a shortest path, and it does not directly support edge deletion.