Python程式檢查給定圖是否是一組樹

假設我們有一個圖，用邊列表表示。我們必須檢查該圖是否是一組樹（森林）。

因此，如果輸入類似於

則輸出將為 True

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

  • 定義一個函式 dfs()。這將獲取節點和前一個節點。

  • 如果節點在 seen 中，則

    • 返回 False

  • 將節點插入 seen 中

  • 對於 e[node] 中的每個相鄰節點 n，執行以下操作：

    • 如果 n 與前一個節點不同，則

      • 如果 dfs(n, node) 為假，則

        • 返回 False

  • 返回 True

  • 從主方法中，執行以下操作：

  • e := 一個空對映

  • 對於邊中的每個起始節點 u 和結束節點 v，執行以下操作：

    • 將 v 插入 e[u] 的末尾

    • 將 u 插入 e[v] 的末尾

  • seen := 一個新的集合

  • 對於 e 中的每個節點，執行以下操作：

    • 如果節點不在 seen 中且 dfs(node, -1) 為假，則

      • 返回 False

  • 返回 True

讓我們看看以下實現以獲得更好的理解：

示例

 即時演示

from collections import defaultdict
class Solution:
   def solve(self, edges):
      e = defaultdict(list)
      for t,f in edges:
         e[t].append(f)
         e[f].append(t)

      seen = set()

      def dfs(node, prev):
         if node in seen:
            return False
         seen.add(node)
      for adj in e[node]:
         if adj != prev:
            if not dfs(adj, node):
               return False
      return True

   for node in e:
      if node not in seen and not dfs(node, -1):
         return False
   return True

ob = Solution()
edges = [[0, 1],[0, 2],[4, 3]]
print(ob.solve(edges))

輸入

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

輸出

True

更新於： 2020年10月8日

216 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告
© . All rights reserved.