【C#】Union-FInd木を実装してみる - はなちるのマイノート

はじめに

今回はUnion-FInd木を実装してみようという記事になります！

これが使える場面は以下のようなとき。

データの集合を素集合(互いに素である集合)に分割してデータを保持したいとき

f:id:hanaaaaaachiru:20200419174308p:plain

例えばきのこの山とたけのこの里の２つの派閥があり、きのこの山とたけのこの里のどちらの派閥にも所属している裏切り者は存在しない場合において、２つの派閥のグループ分けを行うデータ構造です。

早速具体的に見ていきましょう。

はじめに
Union-FInd木の実装方針
まとめる
みつける
コード
使い方
さいごに

Union-FInd木の実装方針

Union-Find木の名前を分割してみると、Union(まとめる)・Find(みつける)となります。

これからもわかる通り、以下の2つの操作を実装する必要があります。

Union: 2つの集合を1つに統合する。
Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。

素集合データ構造 - Wikipedia

これらを効率的に行うために、グループを一つの木で表現します。

f:id:hanaaaaaachiru:20200419175944p:plain

これを考慮しながら2つの操作(クエリ)を実装していきましょう。

まとめる

２つのグループをまとめるには、片方の根から片方の根に辺を張ることで実現できます。

f:id:hanaaaaaachiru:20200419180246p:plain

みつける

同じグループかどうかを判定するには、2つの要素の上を辿って根が同じかどうか調べます。

f:id:hanaaaaaachiru:20200419181059p:plain

コード

これらを実装してみたコードはこちら。

public class UnionFind<T>
{
    private Dictionary<T, Node> _nodes;

    public UnionFind(IEnumerable<T> items = null)
    {
        _nodes = new Dictionary<T, Node>();
        if(items != null)　foreach (var item in items) Add(item);
    }

    /// <summary>
    /// 要素を追加する
    /// </summary>
    public UnionFind<T> Add(T item) {
        _nodes[item] = new Node(item);
        return this;
    }

    /// <summary>
    /// 集合を結合する
    /// </summary>
    public UnionFind<T> Unite(T x, T y)
    {
        Node.Unite(_nodes[x], _nodes[y]);
        return this;
    }

    /// <summary>
    /// 同じ集合に属するか
    /// </summary>
    public bool IsSame(T x, T y)
        => _nodes[x].Find() == _nodes[y].Find();

    /// <summary>
    /// グループに属する頂点の数を返す
    /// </summary>
    public long Size(T x)
        => _nodes[x].Size;

    class Node
    {
        private int _rank;
        private long _size;
        private Node _parent;

        // 常に根がグループに属する頂点数を保持するように
        public long Size => Find()._size;

        public Node(T item)
        {
            _rank = 0;
            _size = 1;
            _parent = this;
        }

        public Node Find()
        {
            if (_parent == this) return this;

            // 根を見つけるとともに、親が根になるようにつなぎ変える
            Node parent = _parent.Find();
            _parent = parent;
            return parent;
        }

        public static bool Unite(Node x, Node y)
        {
            var rootX = x.Find();
            var rootY = y.Find();

            if (rootX == rootY) return false;

            // ランク(木の高さ)が低い方を高い方につなげる
            if (rootX._rank < rootY._rank)
            {
                rootX._parent = rootY;
                rootY._rank = Math.Max(rootX._rank + 1, rootY._rank);
                rootY._size = rootX._size + rootY._size;
            }
            else
            {
                rootY._parent = rootX;
                rootX._rank = Math.Max(rootY._rank + 1, rootX._rank);
                rootX._size = rootX._size + rootY._size;
            }

            return true;
        }
    }
}

使い方

使い方はこんな感じ。

static void Main(string[] args)
{
    // 登場人物たち
    IEnumerable<string> persons = new string[] { "佐藤", "鈴木", "高橋" };

    var trees = new UnionFind<string>(persons);

    // 後から人物を追加
    trees.Add("田中")
        .Add("伊藤");

    // きのこの山グループ
    trees.Unite("佐藤", "鈴木")                         // 佐藤・鈴木は同じグループ
        .Unite("鈴木", "高橋");                         // 鈴木・高橋は同じグループ

    // たけのこの里グループ
    trees.Unite("田中", "伊藤");                        // 田中と伊藤は同じグループ

    Console.WriteLine(trees.IsSame("佐藤", "高橋"));    // true
    Console.WriteLine(trees.IsSame("佐藤", "伊藤"));    // false
}