我目前正在将networkx库用于带有BFS和DFS的Python。我需要获取一棵树,然后对其进行探索以获取从起点到终点的路径。
对于BFS部分,我正在使用bfs_successors
,它从源头开始进行广度优先搜索中的后继迭代器。
对于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)]
这是从头到尾的节点列表。
IIUC,您对寻找被nx.bfs_successors
鼓励的所有继任者并不真正感兴趣,因为您只需要源节点和目标节点之间的路径。
为此,您可以找到shortest path(在有多个的情况下:]
nx.shortest_path(G, source, target)
或找到它们之间的所有简单路径:
nx.all_simple_paths(G, source, target)
这将返回在两个节点之间具有所有简单路径的生成器。