クラスカル法

2022年8月1日

問題

頂点数が $\small N$、辺の数が $\small M$ のグラフでそれぞれの辺の重みが $\small W $ であるとき、最小全域木を求める。

アルゴリズム

1. グラフ $ G = (V, E) $ の辺 $ e_i $ を重みの昇順に整列する。
2. 最小全域木の辺の集合を $K$ とし、それを空に初期化する。
3. $ i=1, 2, …, |E| $ の順番に $ |K| $ が $ |V|-1 $ になるまで $ K \cup \{e_i\} $ が閉路にならないような $ e_i $ を $ K $ に追加する。

コード例（Python）

def kruskal(n, edgeList):
    uft = UnionFind(n)
    MST = []
    edgeList.sort()
    for edge in edgeList:
        x, y, w = edge
        if not uft.issame(x, y):
            uft.unite(x, y)
            MST.append(edge)
    return MST