我正在编写一个函数来检查图是否包含环。
它被表示为一个列表的列表,其中每个节点连接的所有节点的索引都列出来。节点从1开始枚举(任务要求)。
在检查图[[2, 3],[],[4],[]]时,程序正确地进入了第一个列出的节点,但在第二次迭代中,它假定adjlist [node-1]是值为3的int而不是数组(或至少是int = 2)。
我错过了什么?
代码:
它被表示为一个列表的列表,其中每个节点连接的所有节点的索引都列出来。节点从1开始枚举(任务要求)。
在检查图[[2, 3],[],[4],[]]时,程序正确地进入了第一个列出的节点,但在第二次迭代中,它假定adjlist [node-1]是值为3的int而不是数组(或至少是int = 2)。
我错过了什么?
代码:
def is_acyclic(adjlist: List, visited: List, path: List) -> bool:
'''
:param adjlist: list representation of a graph; eg: [[2, 3], [], [4], []]
:param visited: visited nodes
:param path: visited nodes in current iteration
:return: the graph does not contain a cycle
'''
for node in range(1, len(adjlist)+1):
if node not in visited:
visited.append(node)
path.append(node)
for child in adjlist[node-1]:
if child in path:
return False
elif child not in visited:
if is_acyclic(adjlist[node-1], visited, path) is False:
return False
path.remove(node)
return True