CODEWITHSUNDEEP
pythongraphnetworkxdepth-first-searchbreadth-first-search
hellomynameisA
hellomynameisA

Reputation: 634

convert output from dictionary to list with bfs and dfs networkx

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.

For the BFS part I am using bfs_successorsand it returns an iterator of successors in breadth-first-search from source.

For the DFS part I am using: dfs_successors and it returns a dictionary of successors in depth-first-search from source.

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)

and I get this:

{(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)]

which is the list of nodes from start to end.

Upvotes: 0

Views: 686

Answers (1)

yatu
yatu

Reputation: 88285

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.

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.

Upvotes: 1

Related Questions