Pythonのグラフでクリティカルエッジと疑似クリティカルエッジを見つける方法

問題の概要

頂点 0 から n − 1 までの番号が付いた n 個の頂点を持つ無向グラフが与えられ、各辺には重みが設定されているものとします。このグラフをもとに、最小全域木(MST)に含まれる「クリティカルエッジ」と「疑似クリティカルエッジ」を特定します。

クリティカルエッジとは、その辺を削除すると MST の総重みが増加してしまう辺のことです。一方、疑似クリティカルエッジとは、すべての MST に必ず含まれるわけではないものの、何らかの MST には現れ得る辺のことです。ここでは、入力として与えられたグラフに対して、該当する辺のインデックスを求めます。

たとえば、次のようなグラフが入力として与えられたとします。

頂点数が 5 の場合、出力は [[], [0, 1, 2, 3, 4]] となります。このグラフにはクリティカルエッジが存在せず、すべての辺が疑似クリティカルエッジです。すべての辺が同じ重みを持つため、5 本のうち任意の 3 辺を選べば必ず MST が構成できるからです。

アルゴリズムの手順

この問題は、プリム法をベースにした以下の手順で解くことができます。

1. MST の重みを計算する関数 find_mst() を定義します。引数は num_vertices(頂点数)、graph(隣接リスト)、init(初期採用する辺、既定値 None)、exl(除外する辺、既定値 None)です。
2. 補助関数 visit(u) を定義します。
3. k[u] := True とし、頂点 u を訪問済みにします。
4. graph.get(u, []) に含まれる各 (v, w) について次を繰り返します。
   • exl が指定されており、u と v がともに exl に含まれる場合は、その辺をスキップします。
   • v が未訪問であれば、三つ組 (w, u, v) をヒープ tmp に追加します。
5. res := 0 として重みの合計を初期化します。
6. k := 頂点数分の False を要素に持つリストを作成します。
7. tmp := 空のヒープを作成します。
8. init が指定されている場合は、その辺 (u, v, w) を最初に採用し、res += w、k[u] = k[v] = True とした上で visit(u) と visit(v) を呼び出します。
9. 指定されていない場合は visit(0) から探索を開始します。
10. tmp が空になるまで次を繰り返します。
    • ヒープから最小の (w, u, v) を取り出します。
    • u と v が両方すでに訪問済みであれば、サイクルになるためスキップします。
    • res += w として辺を採用し、未訪問の頂点に対して visit() を呼び出します。
11. すべての頂点が訪問済みであれば res を返し、グラフが連結でなければ無限大(inf)を返します。

メイン処理の流れ

1. graph に入力グラフを設定します。
2. temp := find_mst(num_vertices, graph) で通常の MST の重みを求めます。
3. c_edge(クリティカルエッジ用)と p_edge(疑似クリティカルエッジ用)の空リストを用意します。
4. i を 0 から辺の本数まで順に処理します。
   • find_mst(num_vertices, graph, exl=edges[i][:2]) の結果が temp より大きければ、i を c_edge に追加します(その辺を除外すると MST が構成できないか、重みが増加するため)。
   • find_mst(num_vertices, graph, init=edges[i]) の結果が temp と等しければ、i を p_edge に追加します(その辺を強制的に使用しても MST の重みが変わらないため)。
5. [c_edge, p_edge] を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

from heapq import heappop, heappush
from math import inf


def solve(num_vertices, edges):
    graph = dict()
    for u, v, w in edges:
        graph.setdefault(u, []).append((v, w))
        graph.setdefault(v, []).append((u, w))

    temp = find_mst(num_vertices, graph)
    c_edge, p_edge = [], []
    for i in range(len(edges)):
        if find_mst(num_vertices, graph, exl=edges[i][:2]) > temp:
            c_edge.append(i)
        elif find_mst(num_vertices, graph, init=edges[i]) == temp:
            p_edge.append(i)
    return [c_edge, p_edge]


def find_mst(num_vertices, graph, init=None, exl=None):
    def visit(u):
        k[u] = True
        for v, w in graph.get(u, []):
            if exl and u in exl and v in exl:
                continue
            if not k[v]:
                heappush(tmp, (w, u, v))

    res = 0
    k = [False] * num_vertices
    tmp = []
    if init:
        u, v, w = init
        res += w
        k[u] = k[v] = True
        visit(u)
        visit(v)
    else:
        visit(0)

    while tmp:
        w, u, v = heappop(tmp)
        if k[u] and k[v]:
            continue
        res += w
        if not k[u]:
            visit(u)
        if not k[v]:
            visit(v)

    return res if all(k) else inf


print(solve(5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]))

入力

5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]

出力

[[], [0, 1, 2, 3, 4]]