0

我需要找到到给定目标的最长路径。数据是一个 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))

我得到主要的路径堆叠在彼此之上。我将如何修复代码以使路径不会堆叠。我希望主要看起来像

[['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是一个列表列表。

4

1 回答 1

0

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

但是，当您只对最长路径感兴趣时，它肯定会链接根和叶（这些节点没有与任何其他节点的链接）。

在下面的代码中，当到达其中的一片叶子时，即当currentNode not in INFOis时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()功能缩短为以下功能。此外，如果不仅有一个最长的路径，此代码还会返回多个路径。

def longest(main):
    return [x for x in main if len(x) == max([len(x) for x in main])]
于 2019-03-24T12:12:20.480 回答