问题描述
我正在尝试查找用户可以通过网站选择的路径。我已使用以下格式表示我的图表:
graph = { 0 : [1, 2], 1 : [3, 6, 0], 2 : [4, 5, 0], 3 : [1], 4 : [6, 2], 5 : [6, 2], 6 : [1, 4, 5]}
我已经实现了深度优先算法,但它需要进行更改才能发挥作用。它需要返回路径,而不仅仅是返回节点的顺序。
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)
该函数返回以下内容:
[[], 0, 1, 3, 6, 4, 2, 5]
而我想要这样的东西:
[[0, 1, 3], [0, 1, 6], [0, 2, 4, 6], [0, 2, 5, 6]]
推荐答案
在传递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)
它返回所有路径。
[[], [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中可以使用列表复制。