使用 bfs 和 dfs networkx 将字典的输出转换为列表

Question

我目前正在将 Python 的 networkx 库与 BFS 和 DFS 一起使用。我需要得到一棵树，然后探索它以获得从起始节点到结束节点的路径。

对于 BFS 部分，我正在使用 bfs_successors它 returns 来自源的广度优先搜索中的后继迭代器。

对于 DFS 部分，我使用的是：dfs_successors 并且它 returns 来自源的深度优先搜索的后继者字典。

我需要从这两种算法中获取从源到端的节点列表。每个节点都是 (x, y) 并且是网格中的一个单元格。

你对如何做有什么建议吗？你能帮帮我吗？

MWE：

DFS = nx.bfs_successors(mazePRIM,start)
print(dict(BFS))

DFS = nx.dfs_successors(mazePRIM, start)
print(DFS)

我明白了：

{(0, 0): [(0, 1), (1, 0)], (1, 0): [(1, 1)], (1, 1): [(1, 2)], (1, 2): [(0, 2), (1, 3)], (0, 2): [(0, 3)]}

{(0, 0): [(0, 1), (1, 0)], (1, 0): [(1, 1)], (1, 1): [(1, 2)], (1, 2): [(0, 2), (1, 3)], (0, 2): [(0, 3)]}

但我需要这样的输出：

[(0, 0), (1, 0), (1, 1), (1, 2), (1, 3)]

这是从头到尾的节点列表。

Answer 1

IIUC 您对查找 nx.bfs_successors 所吸引的所有后继者并不真正感兴趣，因为您只需要源节点和目标节点之间的路径。

为此，您可以找到 shortest path（如果有多个）：

nx.shortest_path(G, source, target)

或者找到它们之间的所有简单路径：

nx.all_simple_paths(G, source, target)

其中 returns 一个生成器，在两个节点之间具有所有简单路径。

使用 bfs 和 dfs networkx 将字典的输出转换为列表

convert output from dictionary to list with bfs and dfs networkx

python

graph

breadth-first-search

depth-first-search

networkx