C#実装（Kruskal法とUnionFind）

クラスカル法（連結グラフの最小全域木を求める）はアルゴリズムがとても分かりやすくて好ましい。参考は例によって蟻本。

・辺の集合から、最小コストのものを見つける

・この辺が、これまで取り出した辺と連結していなかったら使う。連結済なら破棄

→これを辺がなくなるまで繰り返すだけ

連結の有無はUnionFindを使って判定するが、C#にはUnionFindがないので自前で用意した。連結リストで表現できればスマートだし、上限の指定も不要になるのだが、書くのが面倒なので配列を使うことに。

    /// <summary>
    /// union find, positive int only
    /// </summary>
    public class UnionFind
    {
        private int[] data;

        public UnionFind(int size)
        {
            data = new int[size];
            for (int i = 0; i < size; i++) data[i] = -1;
        }

        public bool Unite(int x, int y)
        {
            x = Root(x);
            y = Root(y);

            if (x != y)
            {
                if (data[y] < data[x])
                {
                    var tmp = y;
                    y = x;
                    x = tmp;
                }
                data[x] += data[y];
                data[y] = x;
            }
            return x != y;
        }

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

        private int Root(int x)
        {
            return data[x] < 0 ? x : data[x] = Root(data[x]);
        }
    }

これを使って実装する。最小コストを順次取り出したいので、辺情報の格納にはSortedSetを利用した。リストでもいいのかもしれないが、ソートがQuckSortなので最悪ケースがO(N^2)になってしまうと考えた。

SortedSetが平衡二分木なので、計算量は辺の追加が平均・最悪ともにO(LogN)、コスト算出がほぼO(N)のはず。（UnionFindはほぼ定数と考えて良いらしい）

    /// <summary>
    /// Vertices index should be positive number
    /// </summary>
    public class Kruskal
    {
        SortedSet<ComparablePair<int, Tuple<int, int>>> pathSet = new SortedSet<ComparablePair<int, Tuple<int, int>>>();

        private int _maxIndex = 1;
        public Kruskal(int maxIndex)
        {
            _maxIndex = maxIndex;
        }

        public void AddPath(int s, int t, int cost)
        {
            var tuple = new Tuple<int, int>(s, t);
            pathSet.Add(new ComparablePair<int, Tuple<int, int>>(cost, tuple));
        }

        public int GetCost()
        {
            int ret = 0;
            var unionFind = new UnionFind(_maxIndex + 1);

            foreach (var path in pathSet)
            {
                int cost = path.Item1;
                int vertex1 = path.Item2.Item1;
                int vertex2 = path.Item2.Item2;

                if (!unionFind.IsSameGroup(vertex1, vertex2))
                {
                    unionFind.Unite(vertex1, vertex2);
                    ret += cost;
                }
            }

            return ret;
        }
    }