在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。
- 如果节点在路径中,则
- 在路径[node]之后,当(i – path[node])为奇数时返回真。
- 如果节点已被访问,则
- 返回False。
- 标记节点为已访问。
- path[node]:= i。
- 对于数组中的每个c,执行以下操作:
- 如果dfs(c, i + 1) 为真,则
- 返回True。
- 如果dfs(c, i + 1) 为真,则
- 删除路径[node]。
- 返回False。
- 从主方法执行以下操作-
- visited := 新集合,path:=新映射
- 对于i在数组大小的范围内,执行以下操作:
- 如果dfs(i, 0) 为真,则
- 返回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