gpt4 book ai didi

Python 从图中获取所有路径

转载 作者:行者123 更新时间:2023-12-04 15:24:12 24 4
gpt4 key购买 nike

我试图找到用户可以通过网站的路径。我已经使用这种格式表示我的图表:

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 中对我有用。

关于Python 从图中获取所有路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62656477/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com