Python程式檢查圖中是否存在奇數長度環

假設我們有一個無向圖，我們需要檢查是否可以在其中找到奇數長度的環。

所以，如果輸入類似於 adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

那麼輸出將是 True，因為存在奇數長度的環，例如 [0, 1, 3, 4, 2]、[1, 3, 4]、[2, 3, 4]。

為了解決這個問題，我們將遵循以下步驟 -

• 定義一個函式 dfs()。它將接收節點 i 作為引數。
• 如果節點在路徑中，則
  • 當 (i - path[node]) 為奇數時返回 true
• 如果節點已被訪問，則
  • 返回 False
• 標記節點為已訪問
• path[node] := i
• 對於 arr[node] 中的每個 c，執行以下操作：
  • 如果 dfs(c, i + 1) 為 true，則
    • 返回 True
• 刪除 path[node]
• 返回 False
• 在主方法中執行以下操作 -
• visited := 一個新的集合，path :=一個新的對映
• 對於範圍從 0 到 arr 大小的 i，執行以下操作：
• 如果 dfs(i, 0) 為 true，則
• 返回 True
• 返回 False

示例（Python）

讓我們看看以下實現，以便更好地理解 -

 即時演示

class Solution:
   def solve(self, arr):
      def dfs(node, i):
         if node in path:
            return (i - path[node]) % 2 == 1
         if node in visited:
            return False
         visited.add(node)
         path[node] = i
         for c in arr[node]:
            if dfs(c, i + 1):
               return True
         del path[node]
         return False
      visited, path = set(), {}
      for i in range(len(arr)):
         if dfs(i, 0):
            return True
      return False
ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))

輸入

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

輸出

True

Arnab Chakraborty

更新於: 2020年12月12日

395 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始