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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始