全路径算法中的 Python 和列表可变性

Question

我一直在研究基于 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 的新手!

Answer 1

您没有具体说明症状是什么。是生成的东西错了，还是 uniquePaths 错了？看起来该函数生成了正确的路径，但在该函数的末尾，uniquePaths 的路径比应有的少得多，而且它们都是空的。

路径不够的原因是 uniquePaths.extend(uniqueTreePaths) 缩进不正确。

你在这里的问题是，visited 是一个可变列表。在 Python 中，所有列表都是可变的。事实上，这就是该算法起作用的原因。 visited 被视为恰好是路径的堆栈。当您多次将 visited 附加到 uniqueTreePaths 时，您实际上是在一遍又一遍地附加同一个对象。当你修改visited时，所有的都被修改了。

要解决此问题，您应该附加列表的副本。这将在内存方面相当昂贵，但您想要图形中的所有唯一路径，因此您应该已经意识到这一点。您可以使用 uniqueTreePaths.append(list(visited)) 从 visited 中创建一个新的 list 对象。我实际上会用它创建一个元组，这样它就不能被修改:uniqueTreePaths.append(tuple(visited))。