如何在python的字典中从一对(父，子)中恢复路径?

Question

我有一个字典key:set

key是具有字符串的子节点，其value是包含其父节点字符串的set。

例如

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

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

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

在此示例中，结果将是

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

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

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

你可以阅读这篇文章，了解 python 中 bfs 和 dfs 的解释和实现。