在Python中查找包含目标的最短周期长度的程序

假设我们有一个有向图的邻接表，其中索引i处的每个列表表示从节点i连接的节点。我们还有一个目标值，我们必须找到包含目标的最短循环的长度。如果没有解决方案，则返回-1。

因此，如果输入如下所示：

目标= 3，则输出将为3，因为该循环是节点1-> 2-> 3-> 1。请注意，还有另一个循环0-> 1-> 2-> 3-> 0，但这不是最短的循环。

为了解决这个问题，我们将按以下步骤进行 –

visited：一个新集
l：具有元素目标的列表。
length：0
while l不为空，执行以下操作
- length：= length + 1
- nl：新列表
- 对于l中的每个u，请执行以下操作
  - 对于u中的每个v，请执行以下操作
  - 如果v与目标相同，则
    - 返回长度
  - 如果v被访问，则
    - 进入下一次迭代
  - 将v标记为visited
  - 在nl的末尾插入v
- l：= nl
返回-1

让我们看一下以下实现以更好地理解 –

更多Python相关文章，请阅读：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))