Union-Find書き直し(C#)

前々回のエントリで、Union-Findの効率が少し悪いとコメントをいただいた。確かに、実務上の問題は小さそうだが、このデータの持ち方はイマイチかもしれない。

そこで、次のように書き直してみた。

• 各ノードにParentとRank情報を持つ
• 配列ではなくツリー構造にする
• それに伴い、上限設定が不要に
• Intではなくobjectを受け付ける

objectなので、型が異なるもの同士もグループ化できる。

var uf = new UnionFind();

Assert.IsFalse(uf.IsSameGroup(1, "1"));
Assert.IsFalse(uf.IsSameGroup("2", 2));
Assert.IsFalse(uf.IsSameGroup("two", 2));

uf.Unite(1, "1");
uf.Unite(2, "2");
uf.Unite(2, "two");

Assert.IsTrue(uf.IsSameGroup(1, "1"));
Assert.IsTrue(uf.IsSameGroup("2", 2));
Assert.IsTrue(uf.IsSameGroup("two", 2));   //2と"two"が同グループになる
Assert.IsTrue(uf.IsSameGroup("2", "two"));

ソースコードはこちら。たぶん、ならし計算量がO(α(n))、ワーストケースがO(n)だろうか。

※α(n)：アッカーマン関数の逆関数と蟻本に書いてるがよくわからない。O(log(n))より速いらしい

    public class UnionFind
    {
        private class Node
        {
            public Node Parent { get; set; }
            public int Rank { get; set; }
        }

        private Dictionary<object, Node> _dict = new Dictionary<object, Node>();

        private Node Root(object data)
        {
            if (!_dict.ContainsKey(data))
            {
                var node = new Node();
                _dict.Add(data, node);
                return node;
            }
            else
            {
                var node = _dict[data];
                return Find(node);
            }
        }

        private Node Find(Node node)
        {
            if (node.Parent == null) return node;
            return node.Parent = Find(node.Parent);
        }

        public void Unite(IComparable x, IComparable y)
        {
            var xRoot = Root(x);
            var yRoot = Root(y);
            if (xRoot == yRoot) return;

            if (xRoot.Rank < yRoot.Rank)
            {
                xRoot.Parent = yRoot;
            }
            else
            {
                yRoot.Parent = xRoot;
                if (xRoot.Rank == yRoot.Rank) xRoot.Rank++;
            }
        }

        public bool IsSameGroup(IComparable x, IComparable y)
        {
            return Root(x) == Root(y);
        }
    }