Найдите путь между двумя значениями в словаре в Python - PullRequest
Новая
       15

Найдите путь между двумя значениями в словаре в Python

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

Я пытаюсь найти путь между двумя элементами в словаре . Позвольте мне объяснить ситуацию. Используя NetworkX , я создал график и используя bfs_successors и dfs_successors, я создал два деревьев , сохраненных в двух словарях , как вы можете увидеть 

BFS = 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,3). Как я могу его получить?

Итак, мне нужна функция для поиска конечного узла и возврата пути между началом и концом.

И можно ли записать это так? 

[(0, 0), (1, 0), (1, 1), (1, 2), (1, 3)]

1 Ответ

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

Я думаю, что идея networkx (хотя я никогда ее не использовал), вероятно, заключается в том, что вы использовали бы такую ​​функцию, как shortest_path, чтобы найти путь между двумя конкретными c узлами, и вы использовали бы только dfs / bfs, если вам нужен исчерпывающий список всех доступных узлов.

Тем не менее, если вы хотите развернуть свою собственную DFS, используя словарь, полученный из этих функций, вот пример: 

>>> from typing import Dict, List, Tuple
>>>
>>>
>>> def dfs(
...     graph: Dict[Tuple[int, int], List[Tuple[int, int]]],
...     path: List[Tuple[int, int]],
...     target: Tuple[int, int]
... ) -> List[Tuple[int, int]]:
...     """Given a graph and a starting path, return the
...     complete path through the graph to the target."""
...     if path[-1] == target:
...         return path
...     if path[-1] not in graph:
...         return []
...     for node in graph[path[-1]]:
...         if node in path:
...             continue
...         maybe_path = dfs(graph, path + [node], target)
...         if len(maybe_path):
...             return maybe_path
...     return []
...
>>>
>>> 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)],
...     (1, 3)
... ))
[(0, 0), (1, 0), (1, 1), (1, 2), (1, 3)]
...