使用bfs和dfs networkx将字典的输出转换为列表 [英] convert output from dictionary to list with bfs and dfs networkx
问题描述
我目前正在将networkx库用于带有BFS和DFS的Python。我需要得到一棵树,然后探索它以获取从起始节点到结束节点的路径。
I am currently using networkx library for Python with BFS and DFS. I need to get a tree and then explore it to get a path from a start node to an end node.
对于BFS部分,我正在使用 bfs_successors
,它从源返回广度优先搜索中的后继迭代器。
For the BFS part I am using bfs_successors
and it returns an iterator of successors in breadth-first-search from source.
对于DFS部分,我正在使用: dfs_successors
,它从源返回深度优先搜索的后继字典。
For the DFS part I am using: dfs_successors
and it returns a dictionary of successors in depth-first-search from source.
我需要从两种算法中获得从源到末端的节点列表。每个节点是(x,y),并且是网格中的一个单元。
I need to get a list of nodes from source to end from both the algorithms. Each node is (x, y) and is a cell in a grid.
您对此有任何建议吗?
Do you have any advice about how to do it? Can you help me please?
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)]}
但是我需要这样的输出:
But I need an output like this:
[(0, 0), (1, 0), (1, 1), (1, 2), (1, 3)]
从头到尾的节点列表。
推荐答案
IIUC,您对找到所有受<$ c $鼓励的继任者并不是很感兴趣。 c> nx.bfs_successors ,因为您只需要源节点和目标节点之间的路径。
IIUC you're not really interested in finding all successors encourtered with nx.bfs_successors
, since you only need the path between a source and a target nodes.
为此,您可以找到< href = h ttps://en.wikipedia.org/wiki/Shortest_path_problem rel = nofollow noreferrer>最短路径(如果有多个路径):
For that you can either find the shortest path (in the case there are multiple):
nx.shortest_path(G, source, target)
或查找它们之间的所有简单路径:
Or find all simple paths between them:
nx.all_simple_paths(G, source, target)
这将返回一个生成器,其中包含两个节点之间的所有简单路径。
Which returns a generator with all simple paths between both nodes.
这篇关于使用bfs和dfs networkx将字典的输出转换为列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!