从邻接矩阵中查找所有路径

Question

我不知道该如何解决这个问题。我得到了一个有12个节点A-L的图。17个边缘连接它们。我被告知要找到从A到L的所有路径。我可以遍历一个节点多次，但只能遍历一次边。输出应该打印每个路径和路径总数。

例如,如果只有1个路径。输出应为：

ABCDEFGHIJKL
12

我想一个递归的深度优先搜索函数应该可以解决这个问题，但我就是想不出一个打印每一条路径的方法。例如，如果我的函数找到一个路径ABDL并到达结尾L，它将打印ABDL。然后它回到D并试图找到另一条路径，我如何使它从A再次打印到下一行？

如有任何意见，将不胜感激。谢谢！

Answer 1

或者将信息传递给最后一个节点，这样它就可以在遇到死胡同时打印它所遵循的路径，或者将遵循的路径传递回调用方，这样它就可以在最后打印整个路径。

递归调用子函数并向前传递数据应该是显而易见的...我敢说，直截了当；）

相反，让递归函数接受其子调用的遍历节点列表--遍历子路径列表作为返回值。在函数结束时，如果您是一个子调用，则返回这些路径以及函数本身访问的任何节点路径（附加到其他节点的开头，如果没有对某些节点进行进一步的深度递归，则将单个节点附加到列表中）。

在最后，当您不是子调用时，您将有一个完整的遍历所有路径的列表。打印出来就行了。

例如，假设您想浏览字母[AAA、ABA、ACA、ABC]，而某些路径是无效的（例如，不允许您在A之后遍历C）：

def 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)