最小全域木:Prim Jarnik 法

今回は競技プログラミングに関する記事です。
以前 Prim Jarnik 法に関する記事を公開したのですが、間違えた内容であることが分かったので内容を修正した記事となります。その節はご迷惑をおかけしました。

もうひとつの最小全域木生成アルゴリズムである Kruskal 法の記事はこちら。 katoufujibanana.hatenadiary.jp

表題の Prim Jarnik 法に入ります。計算量は  O(E\ log(V)) です。
スクリプト的には計算量  O(E\ log(E)) なような気もするのですが、  O(log(V)) = O(log(E)) みたいなところあるのでたぶん同じです。本当かな?

Prim Jarnik 法では、以下の手順をくりかえして全域木を構成します。

  1. 好きなノード1つを選ぶ。このノードは手順開始時に到達済ノードとする。
  2. 選んだノードから伸びている辺すべてを heapq に追加する。(優先順位は、辺のコスト)
  3. heapq から辺を pop する。
  4. pop した辺から未到達のノードに到達できる場合、その辺を全域木を構成する辺に追加する。
  5. さらに、先ほど未到達だったノードを到達済ノードに変更し、そのノードから伸びている辺すべてを heapq に追加する。
  6. 3~6 を繰り返す。

この手順で構成された全域木は最小全域木となります。不思議。

手順の 2 の heapq の優先順位を「その辺を選んだ場合の、原点ノードから辺の終端ノードへの最短距離」とするとダイクストラ法になります。原点ノードってなんだ。

スクリプトは以下になります。

import heapq

def prim_jarnik(self, graph):
    n = len(graph)
    min_edges = []
    connected = [False for _ in range(n)]
    connected[0] = True
    connected_num = 1
    q = []
    for i in range(n):
        for cost, i in graph[0]:
            heapq.push(q, [cost, 0, i])

    while connected_num < n:
        c, f, t = heapq.pop(q)
        if connected[f] and not connected[t]:
            connected[t] = True
            connected_num += 1
            min_edges.push([c, f, t])
            for cost, i in graph[t]:
                if not connected[i]:
                    heapq.push(q, [cost, t, i])

    return min_edges

引数に渡す graph は、隣接リスト表現のグラフを渡してあげてください。