查找特定目标的所有路径的递归函数

Question

我需要找到到达给定目标的最长路径。数据是一个 id 字典，其值是指向该 id 的所有 id 的列表。同样值得注意的是，每个 Id 只能指向另一个 id。

我尝试编写一个递归函数，它将遍历每条可能的路径，并将每个唯一路径选项存储到另一个列表，我将从中找到最长的路径。

def create(main, vec, id):
    if (id not in INFO):
        return(main, vec, id)
    else:
        for source in INFO[id]:
            vec.append(source)
            main.append(vec)
            main, vec, id = create(main, vec, source)
        return main,vec,id

和最长的函数

def longest(main):
    longest = 0
    long_list = 0
    for list in main:
        if len(list) > longest:
            long_list = list
            longest = len(list)
    return long_list

做的时候

INFO = {
    'D4': ['B2','B6'],
    'B6': ['D3'],
    'D3': ['F1','A2'],
    'A2': ['G8'],
    'A1': ['C3'],
    'B2': ['E3','A1']}
main, vec, id = create([],[],'D4')
print(longest(main))

我得到了 main 路径，这些路径相互堆叠。我将如何修复代码以使路径不堆叠。我希望让 main 看起来像

[['B2'],
['B2','E3'],
['B2','A1'],
['B2','A1','C3'],
['B6'],
['B6','D3'],
['B6','D3','F1'],
['B6','D3','A2'],
['B6','D3','A2','G8']]

编辑：

将行 main, vec, id = create(main,[],'D4') 更改为 main, vec, id = create([],[],'D4') 以阐明 main 是列表的列表。

Answer 1

由于您的方法是递归的属性，因此很难跟踪当前节点和起始节点（根）之间的路径。

然而，当您只对最长路径感兴趣时，它肯定是 link 根和叶（这些节点没有 link 到任何其他节点） .

在下面的代码中，当到达其中一个叶子时，即当 currentNode not in INFO 为 true 时，我向上移动并记录到达根的路径。

def create(pathListRef, currentNode, rootNode):
    # pathListRef is the reference to the list containing the paths between all leaves and the root.
    # currentNode holds the current node, e.g. "D3"
    # rootNode holds reference to the root node, i.e. "D4"

    if (currentNode not in INFO):
        # We have reached on of the leaves

        reverseNode = currentNode
        # reverseNode is used to keep track of at which node we are when traveling back to the root.

        path = []
        # holds the relative path between the leave and reverseNode

        while reverseNode is not rootNode:
            # As long as we have not reached the root

            path.insert(0, reverseNode)
            # Prepend (like append, but at the start of the list) the reverseNode to the relative path

            reverseNode = list(INFO.keys())[[i for i,x in enumerate(list(INFO.values())) if reverseNode in x][0]]
            # Get the node linked with the reverseNode and move forward to that one. In essence get the key, where the value contains (since it is a list) the reverseNode.

        pathListRef.append(path)
        # We are at the root, so add the relative path to the final paths list
        return

    # This is only executed when we are not at the leave yet (since we return when we are at a leave)
    for source in INFO[currentNode]:
        create(pathListRef, source, rootNode)

用法如下：

myList = []
startNode = "D4"
create(myList, startNode, startNode)
print(myList)  # -> [['B2', 'E3'], ['B2', 'A1', 'C3'], ['B6', 'D3', 'F1'], ['B6', 'D3', 'A2', 'G8']]

通过使用您的 longest() 函数，您将获得：

print(longest(myList))  # -> ['B6', 'D3', 'A2', 'G8']

顺便说一句，可以将 longest() 函数缩短为以下函数。此外，此代码还 returns 多个路径，如果最长的路径不只有一个的话。

def longest(main):
    return [x for x in main if len(x) == max([len(x) for x in main])]

查找特定目标的所有路径的递归函数

Recursive function to find all paths to a specific target

python

recursion

path

longest-path