Pythonでエッジが最小全域木(MST)に含まれるかどうかを判定するプログラム

問題概要

無向グラフを表す2次元配列 edges が与えられているとします。配列の各要素は1本のエッジを表し、(u, v, w) という形式を持ちます。これは「ノード u と v が接続されており、そのエッジの重みが w である」ことを意味します。

さらに、整数 a と b が与えられ、これらはエッジ (a, b) を指します。求めたいのは、エッジ (a, b) が最小全域木(MST: Minimum Spanning Tree)の一部になり得るかどうかの判定です。

前提条件: グラフは連結であり、エッジ (a, b) は必ずグラフ内に存在するものとします。

入力例

[[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]],
a = 0
b = 2

この場合、出力は True になります。

解法のアプローチ

この問題を解くカギとなるのは、最小全域木の重要な性質(カット特性)です。

エッジ (a, b) の重みを weight としたとき、a から b への経路が「重みが weight 未満のエッジだけ」で構成されてしまう場合、エッジ (a, b) はどの最小全域木にも含まれません。なぜなら、そのような経路が存在すれば、エッジ (a, b) をその経路で置き換えることで、より総重みの小さい全域木が作れてしまうからです。

逆に言えば、重みが weight 未満のエッジだけで a から b へ到達できない場合、エッジ (a, b) はある最小全域木に含まれることが保証されます。

したがって、解法は以下の手順になります。

1. エッジ (a, b) 自身の重み weight を取得する。
2. 元の edges から「重みが weight 未満のエッジ」だけを抜き出した部分グラフを作る。
3. その部分グラフ上で a から b への経路が存在するかを DFS(深さ優先探索)で調べる。
4. 経路が存在しなければ True(MSTに含まれ得る)、存在すれば False を返す。

findPath() 関数のロジック

• a と b が同じなら True を返す(到達完了)。
• edges が空なら False を返す(探索失敗)。
• 各エッジ x について:
  • x[2] が -1(使用済みマーク)ならスキップ。
  • x がノード a につながっているなら、反対側のノードを new_a とする。
  • new_a が見つかったら、x を一時的に edges から取り除き、new_a から b へ再帰的に探索する。
  • 探索が成功すれば True を返し、失敗したら x を edges に戻してバックトラックする。

メイン処理(solve)

• edges から条件 ((x[0] == a かつ x[1] == b) または (x[1] == a かつ x[0] == b)) を満たすエッジの重みを weight として取得する。
• edges を「x[2] < weight を満たすエッジのみ」に絞り込む。
• not findPath(edges, a, b) を返す。

実装例

以下のPythonコードで実際の動作を確認できます。

class Solution:
    def findPath(self, edges, a, b):
        if a == b:
            return True
        if not edges:
            return False
        for x in edges:
            if x[2] == -1:
                continue
            new_a = -1
            if x[0] == a:
                new_a = x[1]
            elif x[1] == a:
                new_a = x[0]
            if new_a != -1:
                edges.remove(x)
                if self.findPath(edges, new_a, b):
                    return True
                edges.append(x)
        return False

    def solve(self, edges, a, b):
        weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[2]
        edges = [x for x in edges if x[2] < weight]
        return not self.findPath(edges, a, b)

ob = Solution()
print(ob.solve([
    [0, 2, 100],
    [1, 2, 200],
    [1, 3, 100],
    [2, 3, 300]
], 0, 2))

入力

[
[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]
], 0, 2

出力

True

結果の解釈

この例では、エッジ (0, 2) の重みは 100 ですが、それより軽いエッジは存在しないため、a=0 から b=2 への代替経路は構築できません。よってエッジ (0, 2) は最小全域木に含まれることになり、出力は True となります。

なお、この実装の計算量は最悪情况下 O(E!) に近い指数時間となりうるため、大規模グラフに対しては Union-Find(素集合データ構造)を用いた効率的な実装への置き換えが推奨されます。