在 Python 中的字典中找到两个值之间的路径

Question

我试图在字典中找到两个元素之间的路径。

让我解释一下情况。使用 NetworkX 我创建了一个 graph 并使用 bfs_successors 和 dfs_successors 我创建了两个 trees，保存在两个词典中，如您所见：

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)]}

现在我需要获取 root/start、(0,0) 和结束节点之间的“路径”，例如 (1,3)。我怎样才能得到它？

所以我需要一个函数来搜索结束节点并return开始和结束之间的路径。

有没有可能这样写？

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

边界：我需要使用dfs和bfs。事实上，当我创建 dfs-tree 和 bfs-tree 时，我想定位一个节点（这将是结束节点）并重建它的路径。

提前致谢

Answer 1

我认为 networkx 的想法（虽然我从来没有用过）可能是你会使用像 shortest_path 这样的函数来找到两个特定节点之间的路径，你只会使用如果您想要所有可到达节点的详尽列表，则 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)]

在 Python 中的字典中找到两个值之间的路径

Find a path between two values in a dictionary in Python

python

tree

search

dictionary

networkx