我一直在研究基于 networkx's version 的 python 中的全简单路径算法.目前，我尝试做的唯一更改是让它获取所有节点的所有路径，而不是在 O(n^2) 双循环内进行。
我相信我已经对主要算法进行了排序，但我不太习惯 Python 列表结构的可变性，我认为这就是搞乱算法的原因。
我用 Java 编写了一个类似的程序，所以我知道测试图上应该有多少条路径，但我似乎无法合理地接近这些数字。
def _all_simple_paths_graph(DG, cutoff):
uniquePaths = []
nlist = DG.nodes()
for source in nlist:
uniqueTreePaths = []
if cutoff < 1:
return
visited = [source]
stack = [iter(DG[source])]
while stack:
children = stack[-1]
child = next(children, None)
if child is None:
stack.pop()
visited.pop()
elif len(visited) < cutoff:
if child not in visited:
visited.append(child)
stack.append(iter(DG[child]))
if visited not in uniqueTreePaths:
yield visited
uniqueTreePaths.append(visited)
else: #len(visited) == cutoff:
if visited not in uniqueTreePaths:
yield visited + [child]
uniqueTreePaths.append(visited)
stack.pop()
visited.pop()
uniquePaths.extend(uniqueTreePaths)
谁能告诉我哪里做错了？我相信这与 visited 应该可变的地方和不应该可变的地方有关。但是，我也可能弄错了基本功能，我是 Python 的新手!
请您参考如下方法:
您没有具体说明症状是什么。是生成的东西错了，还是 uniquePaths 错了？看起来该函数生成了正确的路径，但在该函数的末尾，uniquePaths 的路径比应有的少得多，而且它们都是空的。
路径不够的原因是 uniquePaths.extend(uniqueTreePaths) 缩进不正确。
你在这里的问题是，visited 是一个可变列表。在 Python 中，所有列表都是可变的。事实上，这就是该算法起作用的原因。 visited 被视为恰好是路径的堆栈。当您多次将 visited 附加到 uniqueTreePaths 时，您实际上是在一遍又一遍地附加同一个对象。当你修改visited时，所有的都被修改了。
要解决此问题，您应该附加列表的副本。这将在内存方面相当昂贵，但您想要图形中的所有唯一路径，因此您应该已经意识到这一点。您可以使用 uniqueTreePaths.append(list(visited)) 从 visited 中创建一个新的 list 对象。我实际上会用它创建一个元组，这样它就不能被修改:uniqueTreePaths.append(tuple(visited))。
