我正在连接一个函数来检查一个图是否包含一个循环
它表示为每个节点所连接的节点的所有索引的列表。节点从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
这是因为函数是递归调用的。这部分代码不断修剪图形邻接列表:
第一次邻接列表是:
而
adjlist[node-1]
就是[2, 3]
第二次环绕邻接列表是:
而
adjlist[node-1]
就是3
由于2已经在visited中,节点实际上会增加到2。因此,您会看到:
相关问题 更多 >
编程相关推荐