はじめに

あるデータ集合の複数のコネクション情報から、

最終的なグループ集合を高速に計算したいときに、

よく利用されるデータ構造が、

Union Find Tree (素集合データ構造)です。

ja.wikipedia.org

今回は、

このUnion Find Tree (素集合データ構造)の概要と

サンプル実装について紹介したいと思います。

Union Find Tree (素集合データ構造)の概要

Union Find Treeは、

集合を高速に扱うためのデータ構造です。

ei1333.github.io algo-logic.info pyteyon.hatenablog.com

各集合が共通のデータを持たないため、

素集合データ構造とも呼ばれます。

ja.wikipedia.org

Tree形状でデータの集合を表し、

つながっているデータは同じ集合だとみなします。

uniteという操作で２つのデータを同じ集合にしたり、

issameという操作で２つの要素が、同じグループかどうかを判定できます。

Union Find Treeは、下記の２つの工夫により、

高速に集合を扱うことができます。

下記の２つを実装することにより、root操作が

O(1)になります。

1. Union by size

できるだけTreeの長さを短くするために、２つのTreeをunionするときには、

サイズが小さい方のTreeを、大きい方のrootにつなげるようにします。

これにより、Treeの高さを小さく保つことができ、

rootの探索が高速化されます。

2. 経路圧縮 (Path compression)

ある値のrootを探索する途中で、

親として辿ってきた値の親を

xのrootとして設定することで、

長いTreeを小さく保つことができ、

こちらもrootの探索が高速化できます。

Union Find Treeの各操作と計算量

操作	内容
unite(x, y)	xとyを同じグループにする。すでに同じグループだった場合false, 今回の操作を同じグループにできた場合、trueを返す
issame(x, y)	xとyが同じグループかどうかを判定する
root(k)	kが所属する集合(root)を返す
size(k)	kが所属する集合のサイズを返す
members(k)	kが所属するグループのメンバーを返す
roots()	すべてのrootのリストを返す
group_size()	グループの数を返す
all_group_members()	すべてのグループとそのメンバーを返す

Juliaによるサンプル実装

下記のように、JuliaでUnionFindを実装できます。

struct UnionFind
    parent::Vector{Int} # Parent index of each index, when -1, it is root
    size::Vector{Int} # group size of each index
    UnionFind(N) = new(fill(-1, N), fill(1, N))
end

function root!(uf::UnionFind, x::Int)
    if uf.parent[x] == -1
        return x
    else
        # Path compuression   
        # Set the parent of the values traced from x as the root of x.
        return uf.parent[x] = root!(uf, uf.parent[x])
    end
end

function unite!(uf::UnionFind, x::Int, y::Int)
    x_root = root!(uf, x)
    y_root = root!(uf, y)
    x_root == y_root && return false  # these has already same root
    if uf.size[x_root] < uf.size[y_root] # union by size
        uf.parent[x_root] = y_root
        uf.size[y_root] += uf.size[x_root]
        uf.size[x_root] = uf.size[y_root] 
    else
        uf.parent[y_root] = x_root
        uf.size[x_root] += uf.size[y_root]
        uf.size[y_root] = uf.size[x_root] 
    end
    return true
end

function members(uf::UnionFind, x::Int)
    x_root = root!(uf, x)
    return [x for x in 1:length(uf.parent) if root!(uf, x) == x_root]
end

function all_group_members(uf::UnionFind)
    group_members = Dict{Int, Vector{Int}}()
    for x in 1:length(uf.parent)
        x_root = root!(uf, x)
        haskey(group_members, x_root) || (group_members[x_root] = Int[])
        push!(group_members[x_root], x)
    end
    return group_members
end

roots(uf::UnionFind)=[x for x in 1:length(uf.parent) if uf.parent[x] == -1]
issame(uf::UnionFind, x::Int, y::Int)=root!(uf, x) == root!(uf, y)
size(uf::UnionFind, x::Int)=uf.size[x]
group_size(uf::UnionFind)=length(roots(uf))

上記の実装は下記のように利用可能です。

uf = UnionFind(5)
@show uf
# uf = UnionFind([-1, -1, -1, -1, -1], [1, 1, 1, 1, 1])
@show unite!(uf, 2, 3)
# unite!(uf, 2, 3) = true
@show unite!(uf, 2, 3)
# unite!(uf, 2, 3) = false
@show uf
# uf = UnionFind([-1, -1, 2, -1, -1], [1, 2, 2, 1, 1])
@show root!(uf, 2)
# root!(uf, 2) = 2
@show issame(uf, 1, 2)
# issame(uf, 1, 2) = false
@show issame(uf, 2, 3)
# issame(uf, 2, 3) = true
@show size(uf, 2)
# size(uf, 2) = 2
@show size(uf, 3)
# size(uf, 3) = 2
@show members(uf, 1)
# members(uf, 1) = [1]
@show members(uf, 2)
# members(uf, 2) = [2, 3]
@show members(uf, 3)
# members(uf, 3) = [2, 3]
@show members(uf, 4)
# members(uf, 4) = [4]
@show roots(uf)
# roots(uf) = [1, 2, 4, 5]
@show group_size(uf)
# group_size(uf) = 4
@show all_group_members(uf)
# all_group_members(uf) = Dict(5 => [5], 4 => [4], 2 => [2, 3], 1 => [1])