Pythonでターゲットノードを含む最短サイクルの長さを求める方法(BFS活用)

問題の概要

有向グラフの隣接リストが与えられます。各インデックス i のリストには、ノード i から直接接続されているノードの一覧が格納されています。さらに、探索対象となる値(target)も与えられます。この課題では、target を含むサイクル(閉路)の中で最も短いものの長さを求めます。該当するサイクルが存在しない場合は -1 を返してください。

具体例

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

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

target = 3 の場合、出力は 3 になります。これは、ノード 1 → 2 → 3 → 1 というサイクルが存在するためです。なお、0 → 1 → 2 → 3 → 0 という別のサイクルもありますが、こちらの方が長いため最短としては採用されません。

解き方のアプローチ

この問題は幅優先探索(BFS)を使うことで効率的に解けます。target ノードから出発してグラフを段階的に探索し、再び target に戻ってきた時点の深さ(ステップ数)が、そのまま最短サイクルの長さになります。

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

• visited := 訪問済みノードを記録する新しい集合
• l := target を要素に持つリスト(現在の探索層)
• length := 0(サイクルの長さ)
• l が空でない間、以下を繰り返す:
  • length を 1 増やす
  • nl := 次の探索層を格納する新しいリスト
  • l 内の各ノード u について:
    • graph[u] 内の各ノード v について:
      • v が target と一致したら、length を返す(サイクル発見)
      • v が訪問済みの場合はスキップして次へ進む
      • v を visited に追加し、nl の末尾に挿入する
  • l := nl(探索層を次に進める)
• ループが終了しても見つからなければ、-1 を返す

ポイントは、visited 集合で一度訪れたノードを二度と探索しないようにすることです。これにより無駄な探索が省かれ、最初に target へ戻ってきた経路が必ず最短になります。

Pythonでの実装例

それでは、上記の手順を実装してみましょう。

class Solution:
    def solve(self, graph, target):
        visited = set()
        l = [target]
        length = 0

        while l:
            length += 1
            nl = []
            for u in l:
                for v in graph[u]:
                    if v == target:
                        return length
                    if v in visited:
                        continue
                    visited.add(v)
                    nl.append(v)
            l = nl

        return -1

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

入力

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

出力

3

計算量の評価

このアルゴリズムは、各ノードと各エッジをそれぞれ最大1回ずつ処理するため、時間計算量は O(V + E)(Vはノード数、Eはエッジ数)です。また、訪問済み集合と探索キューに必要なメモリから、空間計算量は O(V) となります。グラフの規模が大きくなっても効率よく動作する、実用的な手法と言えるでしょう。