如何从 python 字典中的一对 (parent, child) 恢复路径？

Question

我有字典key:set

key 是一个带有字符串的 child 节点，它的 value 是一个 set 包含它的 parent 节点的字符串。

例如

startnode = "hit"
endnode = "cog"
mydict =  {'hot': {'hit'}, 'dot': {'hot'}, 'lot': {'hot'}, 
       'dog': {'dot'}, 'log': {'lot'}, 'cog': {'dog', 'log'}}

'cog': {'dog', 'log'}：表示dog和log都指向child节点cog

如何从任意两个节点恢复所有可能的路径？

在此示例中，结果将为

res = [["hit","hot","dot","dog","cog"],
       ["hit","hot","lot","log","cog"]]

我尝试使用 loop，但我失败了，因为每个 child 都可以有 arbitrary parent。有什么想法吗？

Answer 1

首先创建一个字典，键是父项，值是键的子项。然后运行任何寻路算法（bfs或dfs）找到所有可能的路径。

根据您拥有的内容创建字典：

from collections import defaultdict
adjacency = defaultdict(set)
for key in mydict:
   for node in mydict[key]:
     adjacency[node].add(key)

结果是：

defaultdict(set,
            {'dog': {'cog'},
             'dot': {'dog'},
             'hit': {'hot'},
             'hot': {'dot', 'lot'},
             'log': {'cog'},
             'lot': {'log'}})

关于bfs和dfs的解释和实现可以阅读this篇文章python。

如何从 python 字典中的一对 (parent, child) 恢复路径？

How to recover the path from a pair of (parent, child) in dictionary in python?

python

dictionary

breadth-first-search