用 Python 编写程序检查给定的图是否是一组树

pythonserver side programmingprogramming更新于 2026/1/14 23:40:17

假设我们有一个图，表示为边列表。我们必须检查该图是否是一组树(森林)。

因此，如果输入类似

则输出将为 True

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

定义一个函数 dfs() 。这将获取节点，prev
如果节点在seen中，则
- 返回False
将节点插入seen中
对于e[node]中的每个相邻节点n，执行
- 如果n与prev不同，则
  - 如果dfs(n, node)为false，则
    - 返回False
返回True
从main方法中，执行以下操作−
e := an空映射
对于边中的每个起始节点 u 和终止节点 v，执行
- 在 e[u] 末尾插入 v
- 在 e[v] 末尾插入 u
已看到 := 一个新集合
对于 e 中的每个节点，执行
- 如果未看到节点且 dfs(node, -1) 为 false，则
  - 返回 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))