Pythonでターゲットを保持している最短のサイクル長を見つけるプログラム

有向グラフの隣接リストがあるとします。ここで、インデックスiの各リストは、ノードiからの接続されたノードで表されます。目標値もあります。ターゲットを含む最短サイクルの長さを見つける必要があります。解決策がない場合は-1を返します。

したがって、入力が次のような場合

target =3.の場合、サイクルはノード1-> 2-> 3-> 1であるため、出力は3になります。別のサイクル0-> 1-> 2-> 3-> 0があることに注意してください。ただし、これは最短ではありません。

これを解決するには、次の手順に従います-

• 訪問：=新しいセット
• l：=要素ターゲットのリスト。
• 長さ：=0
• lが空ではない場合は、
  • 長さ：=長さ+ 1
  • nl：=新しいリスト
  • lの各uについて、
    • グラフ[u]の各vについて、
      • vがターゲットと同じ場合、
        • 戻りの長さ
      • vにアクセスした場合、
        • 次の反復に進む
      • vを訪問済みとしてマーク
      • nlの最後にvを挿入
  • l：=nl
• 戻り値-1

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

例

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