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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告