преобразовать вывод из словаря в список с помощью bfs и dfs networkx - PullRequest
Новая
       89

преобразовать вывод из словаря в список с помощью bfs и dfs networkx

0 голосов
/ 16 июня 2020

В настоящее время я использую библиотеку networkx для Python с BFS и DFS. Мне нужно получить дерево, а затем исследовать его, чтобы получить путь от начального узла до конечного узла.

Для части 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)]

- список узлов от начала до конца.

1 Ответ

1 голос
/ 16 июня 2020

IIU C на самом деле вы не заинтересованы в поиске всех преемников, заключенных с nx.bfs_successors, поскольку вам нужен только путь между исходным и целевым узлами.

Для этого вы можете либо найти кратчайший путь (в случае их нескольких): 

nx.shortest_path(G, source, target)

Или найдите все простые пути между ними: 

nx.all_simple_paths(G, source, target)

Что возвращает генератор со всеми простыми пути между обоими узлами.

...