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

Question

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

对于BFS部分，我使用的是 bfs_successors并从源头返回一个breadth-first-search的继任者迭代器。

对于DFS部分，我使用的是 dfs_successors 它从源头返回一个深度优先搜索的继承者字典。

我需要从两个算法中得到一个从源头到终点的节点列表。每个节点是(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你并不是真的对找到所有继任者encourtered感兴趣 nx.bfs_successors因为你只需要源节点和目标节点之间的路径。

为此，你可以找到 最短路径 在有多个的情况下）。

nx.shortest_path(G, source, target)

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

nx.all_simple_paths(G, source, target)

返回一个包含两个节点之间所有简单路径的生成器。