Python程序：查找包含目标节点的最短环长度

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

例如，输入：

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

为了解决这个问题，我们将遵循以下步骤：

  • visited := 一个新的集合
  • l := 一个包含目标元素的列表。
  • length := 0
  • 当l非空时，执行：
    • length := length + 1
    • nl := 一个新的列表
    • 对于l中的每个u：
      • 对于graph[u]中的每个v：
        • 如果v与目标相同，则
          • 返回length
        • 如果v已访问，则
          • 跳过本次迭代
        • 标记v为已访问
        • 将v插入nl的末尾
    • 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

更新于：2020年12月2日

336 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告