最小全域木：Kruskal 法

今日は競技プログラミングに関する記事です。

最小全域木という、なかなか聞きなれない単語ですが、「ある無向グラフがあって、その辺の一部だけを選んで残して木にしたもののうち、もっとも辺のコストの総和が小さいもの」のことを指します。

ひどい実装をすると、辺の数が 個あって、 パターンすべて試して、連結かどうかを毎回判定しそのものの中で最小なものを取得するとかでしょうか。 て。

この最小全域木を求めるアルゴリズムの一つに Kruskal 法というものがあります。

発想としては、辺をそのコストでソートし、コストの小さい方からばらばらになっている木同士をつないでいくように辺を採用していく、というアルゴリズムです。

「この辺を追加すると、木が大きくなるか？（逆に、すでに連結してしまっていないか？）」の判定に、Union-Find を使います。Union-Find については、以下の記事からどうぞ。

katoufujibanana.hatenadiary.jp

それではスクリプトをどうぞ。

def kruskal(self, n, edges):
    edges.sort()
    uft = UnionFindTree(n)
    min_edges = []
    for edge in edges:
        _, f, t = edge
        if uft.leader(f) != uft.leader(t):
            uft.merge(f, t)
            min_edges.append(edge)

    return min_edges

引数の edges には、普段のグラフの表現に使う隣接リスト表現や、隣接行列表現ではなく、ただの辺のリストを渡してください。

辺自体は、要素３つのリストで、頭から順番に

• コスト
• 端点のうち片方のノード番号
• 端点のうちもう片方のノード番号

を持っているという前提でこのスクリプトは書かれています。

雰囲気としてはこんな感じです。

edges = [
  [cost_1, i_1, j_1],
  [cost_2, i_2, j_2],
  [cost_3, i_3, j_3],
  ...,
  [cost_E, i_E, j_E]
]

さて気になる計算量ですが、Union-Find の leader 関数は、とてもとても速いので、結局最初の

    edges.sort()

が律速となります。つまり、 となります。 よりだいぶましですね。