在网上看到这个例子,它是一个dfs函数,它可以在一个图中找到所有的循环。在
我正在尝试将循环部分添加到函数中,这样就不必使用shell来获得结果。 我不熟悉生成器对象,所以不知道如何显示循环。在
使用shell的版本:
def dfs(graph, start, end):
fringe = [(start, [])]
while fringe:
state, path = fringe.pop()
if path and state == end:
yield path
continue
for next_state in graph[state]:
if next_state in path:
continue
fringe.append((next_state, path+[next_state]))
>>> graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }
>>> cycles = [[node]+path for node in graph for path in dfs(graph, node, node)]
>>> len(cycles)
7
>>> cycles
[[1, 5, 2, 1], [1, 3, 1], [1, 2, 1], [2, 1, 5, 2], [2, 1, 2], [3, 1, 3], [5, 2, 1, 5]]
以下是我的尝试:
^{pr2}$尝试了几个不同的开始和结束节点,结果都一样。在
我的图表和上面一样
graph = { 1: [2, 3, 5], 2: [1], 3: [1], 4: [2], 5: [2] }
输出= 位于0x000001D9CB846EB8的生成器对象dfs
有什么想法吗?在
首先,请修正你的压痕。在
我认为你的问题是由于缺少
[]
来理解列表。在试着换线
cycles = (list([node]+path for node in g for path in dfs(g, node, node)))
到cycles = [[node]+path for node in g for path in dfs(g, node, node)]
这就是你要找的吗?在
您不需要在生成器中返回,所以可以使用列表理解或常规循环遍历它。在
相关问题 更多 >
编程相关推荐