python - Python从图中获取所有路径
问题描述
我试图找到用户可以通过网站采取的路径。我使用这种格式表示我的图表:
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 - 在 sqlalchemy 中删除所有子对象后删除父对象
- javascript - react.js:从另一个组件调用函数
- sql-server - ADODB 错误 800a0bb9;位还是整数?
- spring-boot - 在 Spring 中使用微服务架构
- javascript - 在 gojs 图表中格式化和对齐文本
- html - 使用 Sass CSS 和 FlexBox 垂直堆叠转换后的文本
- python - 使用python的windows和mac应用程序
- c# - JSON Web 令牌 - 如何识别用户?
- ruby-on-rails - 在 Active Admin Rails 中创建新项目时过滤下拉列表
- applescript - 使用 applescript 清除 ITerm2 缓冲区