如何从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'}})

您可以阅读this文章，以了解python中bfs和dfs的解释和实现。