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

Question

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

例如，如果只有 1 个路径。输出应该是:

ABCDEFGHIJKL
12

我认为递归深度优先搜索函数应该能够解决这个问题，但我只是想不出一种打印每条路径的方法。例如，如果我的函数找到路径 ABDL 并到达末尾 L，它将打印 ABDL。然后它返回到 D 并尝试寻找另一条路径，如何才能使其在下一行再次从 A 打印？

如有任何意见，我们将不胜感激。谢谢!

Answer 1

要么将信息传递给最后一个节点，以便它可以在遇到死胡同时打印它所遵循的路径，要么将遵循的路径传递回调用者，以便它可以在末尾打印整个路径。

递归调用子函数并向前传递数据应该是显而易见的......我敢说，很简单；)

如果以相反的方式执行此操作，请让递归函数接受来自其子调用的遍历节点列表 - 遍历子路径列表作为返回值。在函数的末尾，如果您是子调用，请返回它们以及函数本身访问的任何节点路径(附加到其他节点的开头，如果没有进一步的深度递归，则将单个节点附加到列表中已针对某些节点完成)。

最后，当您不是子调用时，您将获得所有经过的路径的完整列表。只需打印出来即可。

例如，假设您想要探索字母 [AAA, ABA, ACA, ABC, ACC]，并且某些路径无效(例如，不允许您在 A 之后遍历 C):

def mypathsearch(路径遍历，当前字母，剩余字母): """采用搜索到的字母字符串、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)