Pythonでグラフを切断する辺（ブリッジ）を見つけるプログラム

問題概要

隣接リスト形式で表された無向グラフが与えられます。graph[i] はノード i に隣接するノードの一覧を表します。このとき、次の条件を満たす辺の本数を求めます。

ある辺を取り除いたとき、グラフが非連結（分断された状態）になる。

このような辺は、グラフ理論では「橋（ブリッジ）」と呼ばれます。

たとえば、入力が次のような場合を考えてみましょう。

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

この場合、出力は 1 となります。ノード 4 はノード 3 との辺によってのみ残りのグラフとつながっているため、この辺を取り除くとノード 4 が孤立してしまうからです。

解法のアプローチ

この問題は、DFS（深さ優先探索）を利用した Tarjan の橋検出アルゴリズムの考え方で効率よく解けます。各ノードの深さ（訪問順序）を記録しながら探索を進め、子孫側の部分グラフから祖先側へ戻る経路が存在するかどうかを判定します。戻る経路が存在しなければ、その辺は橋であると判断できます。

具体的な手順は以下の通りです。

• dfs(curr, pre, d) 関数を定義します（curr：現在のノード、pre：直前に訪れたノード、d：深さ）。

  • ans を無限大で初期化します。

  • dep[curr] に d を記録します。

  • graph[curr] 内の各隣接ノード adj について、次を繰り返します。

    • adj が pre と同じ場合は、何もせず次の反復へ進みます。

    • dep[adj] が -1 以外（訪問済み）の場合は、ans を ans と dep[adj] の最小値で更新します。

    • それ以外（未訪問）の場合は、ans を ans と dfs(adj, curr, d + 1) の戻り値の最小値で更新します。

  • d > 0 かつ d <= ans が成り立つ場合、re を 1 増やします（現在の辺が橋であることを意味します）。

  • ans を返します。

• メイン処理から dfs() を呼び出します。

• dep を、グラフのサイズと同じ長さ・全要素 -1 のリストとして初期化します。

• re を 0 で初期化します。

• dfs(0, -1, 0) を実行します。

• 最後に re を返します。

実装例

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

class Solution:
    def solve(self, graph):
        dep = [-1] * len(graph)
        INF = int(1e9)
        self.re = 0

        def dfs(curr, pre, d):
            ans = INF
            dep[curr] = d
            for adj in graph[curr]:
                if pre == adj:
                    continue
                if dep[adj] != -1:
                    ans = min(ans, dep[adj])
                else:
                    ans = min(ans, dfs(adj, curr, d + 1))
            if d > 0 and d <= ans:
                self.re += 1
            return ans

        dfs(0, -1, 0)
        return self.re

ob = Solution()
print(ob.solve(graph = [
    [0, 2],
    [0, 4],
    [1, 2, 3],
    [0, 3, 4],
    [4],
    [3],
    [2]
]))

入力

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

出力

1

まとめ

DFSで各ノードの深さを追跡しながら、部分グラフから上位へ戻れる経路の有無を調べることで、グラフを分断する辺（橋）を O(V + E) の計算量で検出できます。ネットワークの脆弱性分析や連結性の評価など、さまざまな場面で応用できる重要なテクニックなので、ぜひマスターしておきましょう。