Найти все пути от матрицы смежности

Question

Я не знаю, как именно решить эту проблему. Мне был дан график с 12 узлами A-L. 17 ребер соединяют их. Мне сказали найти все пути от A до L. Я могу пересекать узел несколько раз, но край только один раз. Вывод должен печатать каждый путь и общее количество путей.

Например, если только 1 путь. Вывод должен быть:

ABCDEFGHIJKL 
12 

Я думал рекурсивная глубина первой функция поиска должна быть в состоянии решить, но я просто не могу понять, способ печати каждого пути. Например, если моя функция находит путь ABDL и достигает конца L, он печатает ABDL. Затем он возвращается к D и пытается найти другой путь, как я могу заставить его печатать из A снова на следующей строке?

Любой вход будет оценен. Благодаря!

Answer 1

Либо передайте информацию последнему узлу, чтобы он мог распечатать, какой путь он выполнил, когда он попал в тупик, либо передать последующие пути обратно вызывающему абоненту, чтобы он мог распечатать все пути в конце.

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

Для делать это наоборот, сделать рекурсивная функция принимает список пройденных узлов от своего ребенка calls - список пройденных подпутей в качестве возвращаемого значения. В конце функции, если вы являетесь подзаголовком, возвращайте их вместе с любыми путями узлов, которые посещает сама функция (добавление к началу остальных и добавление отдельных узлов в список, если не требуется дальнейшая рекурсия глубины было сделано для некоторых узлов).

В самом конце, когда вы не являетесь подзаголовком, у вас будет полный список пройденных путей. Просто распечатайте их.

Например, предположим, что вы хотите изучить буквы [AAA, ABA, ACA, ABC, ACC], и некоторые пути являются недействительными (например, вы не разрешается пересекать C после A):

защиту mypathsearch (path_traversed, current_letter, remaining_letters): «» «принимает строку из букв искали, а current_letter характер, и массив символьных массивов, содержащих оставшиеся комбинации букв для каждой позиции» «»

if can_traverse(path_traversed, current_letter): 

    for next_letter in remaining_letters[0]: 
     letters_after = remaining_letters[1:] 

     sub_paths_searched = mypathsearch(
      path_traversed + current_letter, next_letter, letters_after 
     ) 

else: 
    # end of the line 
    print_path_traversed(path_traversed)