Union-Findアルゴリズムと計算科学の話

概要 Union-Findアルゴリズムは、グラフ系でよく使われるアルゴリズムですが、物性物理においても重要な役割を果たします。その実装と使われ方について少しメモしておきます。 Union-Findアルゴリズム 何か2つの物が与えられたとき、それらがある意味において「同じグループに所属するかどうか」が判定できるとき、その関係を同値関係と呼びます。例えば相似などが典型例で、図形Aと図形Bが相似、図形Bと図形Cが相似ならば、図形Aと図形Cも相似です。このように「友達の友達は友達」みたいな関係が同値関係です。とりあえず同値関係を\simで表現することにしましょう。ある集合の要素a,b,cについて、 a\sim a 自分自身とは必ず同じグループ (反射律) a\sim b ならば b \sim a (対称律) a\sim b かつ b \sim c ならば a \sim c (推移律) が成り立つと