find path and convert from dictionary to list

Question

I am 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.

Here's what I've done so far:

BFS = 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.

Do you have any advice about how to do it? Can you help me please?

Does this answer your question? [convert output from dictionary to list with bfs and dfs networkx](https://stackoverflow.com/questions/62412222/convert-output-from-dictionary-to-list-with-bfs-and-dfs-networkx) — rkersh, Jun 16 '20 at 21:20
It looks like you are asking the same question here as in https://stackoverflow.com/questions/62412222. `bfs_successors` or `dfs_successors` does not give you the path from `start` to `end` by itself. You can use `shortest_path` or `all_simple_paths` for that. — rkersh, Jun 16 '20 at 21:25
Hi @rkersh! Yes, I did, but then I found out the answer was not good for what I needed. I tried to change the post and to cancel it, but I couldn't, so I wrote a new one (this) and got the answer I needed — hellomynameisA, Jun 16 '20 at 21:28
The answers below do **not** give you what you asked for in your question. Instead, they give every node that can be reached from `start` using either breadth-first search or depth-first search. — rkersh, Jun 16 '20 at 21:35
So, what do you suggest? I'm sorry, I don't understand what you think I should do — hellomynameisA, Jun 16 '20 at 21:39

Red · Accepted Answer · 2020-06-16T20:01:11.630

1

Use a list comprehension and imply add .keys() to the end of your dictionaries:

DFS = nx.bfs_successors(mazePRIM,start)
print([n for n in dict(BFS).keys()])

DFS = nx.dfs_successors(mazePRIM, start)
print([n for n in DFS.keys()])

You can read more about dictionary keys here:

How to return dictionary keys as a list in Python?

edited Jun 16 '20 at 20:01

answered Jun 16 '20 at 19:55

Red

26,798
7
36
58

Thank you very much! Do you also know how can I get the path between two elements in a dictionary? – hellomynameisA Jun 16 '20 at 20:34
1

Change `.keys()` to `.values()`. – Red Jun 16 '20 at 20:52

score 1 · Answer 2 · answered Jun 16 '20 at 20:06

1

You can simply convert the dictionary keys directly to a list:

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

DFS = nx.dfs_successors(mazePRIM, start)
print(list(dict(DFS).keys()))

answered Jun 16 '20 at 20:06

Gustav Rasmussen

3,720
4
23
53

find path and convert from dictionary to list

2 Answers2