0

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

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

ABCDEFGHIJKL
12

我在想一个递归深度优先搜索功能应该能够解决这个问题，但我只是想不出一种打印每条路径的方法。例如，如果我的函数找到路径 ABDL 并到达末端 L，它会打印 ABDL。然后它回到 D 并试图找到另一条路径，我怎样才能让它在下一行再次从 A 打印？

任何输入将不胜感激。谢谢！

4

1 回答 1

0

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

递归调用子函数并向前传递数据应该很明显......我敢说，直截了当;）

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

最后，当您不是子呼叫时，您将获得一个完整的遍历所有路径的列表。把它们打印出来。

例如，假设您要探索字母 [AAA, ABA, ACA, ABC, ACC]，并且某些路径无效（例如，您不允许在 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)
于 2013-10-07T23:42:01.360 回答