Блог

Мне нужно найти самый длинный путь к заданной цели. Данные представляют собой словарь идентификаторов, значение которого представляет собой список всех идентификаторов, которые указывают на этот идентификатор. Также стоит отметить, что каждый идентификатор может указывать только на один другой идентификатор.

Я попытался написать рекурсивную функцию, которая будет проходить по каждому возможному пути и сохранять каждый уникальный параметр пути в другой список, из которого я найду самый длинный путь.

 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
  

и функция longest

 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 это список списков.

Из-за рекурсивного свойства вашего подхода трудно отслеживать путь между текущим узлом и начальным узлом (root).

Однако, когда вас интересует только самый длинный путь, он, безусловно, связывает корневой и выходной (это узлы, у которых нет ссылки ни на один другой узел).

В следующем коде, при достижении одного из листьев, т.е. когда 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() функцию до следующей. Кроме того, этот код также возвращает несколько путей, если существует не только один самый длинный.

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