2

我一直在研究基于networkx版本的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 还很陌生！

4

1 回答 1

1

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

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

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

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

于 2013-07-04T22:19:41.750 回答