algorithm - python : List all possible paths in graph represented by dictionary

Question

我有一个字典，其中的键代表节点，值代表该键可以遍历到的可能节点。

示例:

dependecyDict = { 'A': ['D'], 'B': ['A', 'E'], 'C': ['B'], 'D': ['C'], 'G':['H']}

我想创建一个新的字典 ChainsDict，它将包含每个“键”可以通过 dependentecyDict 遍历到的所有“值”。

例如，本例程序的输出将是:

ChainsDict = {'A': ['D', 'C', 'B','E'], 'B':['A','D','C','E'], 'C':['B','A','D','E'], 'D':['C','B','A','E'], 'G': ['H']}

我认为使用递归算法是制定解决方案的最佳方法，我尝试修改最短路径遍历算法，如下所示:

def helper(dependencyDict, ChainsDict):path = []
    for key in dependencyDict:
        path = path + [(recursiveRowGen(dependencyDict,key))]
    for paths in path:
        ChainsDict[paths[0]] = paths[1:]
    print(finalLineDict)
def recursiveRowGen(dependencyDict,key,path = []):
    path = path + [key]

        if not key in dependencyDict:
        print("no key: ",key)
        return path
        print(dependencyDict[key])
        for blocking in dependencyDict[key]:
            if blocking not in path:
                newpath = recursiveRowGen(dependencyDict,blocking,path)
                if newpath:
                    return newpath             
    return path

但是，当 dependentecyDict 中的某个键具有多个值时，此代码在捕获正确输出时会出现问题。 我找到了一个 hacky 解决方案，但感觉不太优雅。感谢任何帮助，谢谢!

Answer 1

这是一个递归解决方案:

代码

def get_chain_d(argDict):
    def each_path(i,caller_chain):
        a=[]
        caller_chain.append(i)
        b = argDict.get(i,[])
        for j in b:
            if j not in caller_chain:
                a.append(j)
                a.extend(each_path(j,caller_chain))
        return a

    return {i:each_path(i,[]) for i in argDict}

dependecyDict = { 'A': ['D'], 'B': ['A', 'E'], 'C': ['B'], 'D': ['C'], 'G':['H']}

print(get_chain_d(dependecyDict))

输出:

{'B': ['A', 'D', 'C', 'E'], 'A': ['D', 'C', 'B', 'E'], 'D': ['C', 'B', 'A', 'E'], 'C': ['B', 'A', 'D', 'E'], 'G': ['H']}