Python 从图中获取所有路径

Question

我正在尝试查找用户浏览网站的路径。我用这种格式表示我的图表：

graph = { 0 : [1, 2],
          1 : [3, 6, 0],
          2 : [4, 5, 0],
          3 : [1],
          4 : [6, 2],
          5 : [6, 2],
          6 : [1, 4, 5]}

我已经实现了深度优先算法，但需要对其进行更改才能发挥作用。它需要 return 路径，而不仅仅是节点的顺序。

visitedList = [[]]
def depthFirst(graph, currentVertex, visited):
    visited.append(currentVertex)
    for vertex in graph[currentVertex]:
        if vertex not in visited:
            depthFirst(graph, vertex, visited)
    return visited

traversal = depthFirst(graph, 0, visitedList)
print('Nodes visited in this order:')
print(visitedList)

那个函数return是这个：

[[], 0, 1, 3, 6, 4, 2, 5]

而我想要这样的东西：

[[0, 1, 3], [0, 1, 6], [0, 2, 4, 6], [0, 2, 5, 6]]

Answer 1

在 python 中传递列表时，它不会进行深度复制。使用 list.copy() 在这里真的很有帮助。我不确定这是你想要的，但这是代码：

visitedList = [[]]

def depthFirst(graph, currentVertex, visited):
    visited.append(currentVertex)
    for vertex in graph[currentVertex]:
        if vertex not in visited:
            depthFirst(graph, vertex, visited.copy())
    visitedList.append(visited)

depthFirst(graph, 0, [])

print(visitedList)

它returns所有路径。

[[], [0, 1, 3], [0, 1, 6, 4, 2, 5], [0, 1, 6, 4, 2], [0, 1, 6, 4], [0, 1, 6, 5, 2, 4], [0, 1, 6, 5, 2], [0, 1, 6, 5], [0, 1, 6], [0, 1], [0, 2, 4, 6, 1, 3], [0, 2, 4, 6, 1], [0, 2, 4, 6, 5], [0, 2, 4, 6], [0, 2, 4], [0, 2, 5, 6, 1, 3], [0, 2, 5, 6, 1], [0, 2, 5, 6, 4], [0, 2, 5, 6], [0, 2, 5], [0, 2], [0]]

列表副本在 python3.

中对我有用

Python 从图中获取所有路径

Python get all paths from graph

python

depth-first-search

graph-traversal