Python程式：查詢包含目標節點的最短環長度

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],[]]

輸出

Arnab Chakraborty

更新於：2020年12月2日

336 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習