我目前正在研究递归 DFS，以检索无向和未加权图中两个节点之间的所有路径。它在保存路径的同时递归地获取开始和结束节点以及节点及其相邻节点上的DFS。我想知道是否有更有效的方法来查找所有路径？
问问题
18010 次
2 回答
3
有指数级的简单路径，而 DFS 基本上将它们全部创建为 0，因此您的方法是正确的，尽管很耗时（但这是问题本身的一部分，而不是算法）。
如果存在这样的节点，您可以通过从图形中消除不通向目标的节点来稍微优化它 - 在计算它们之前有效地修剪不成功的搜索。
请注意，如果图形包含循环 - 可能有无限数量的路径（尽管有限数量的简单路径）。请注意，为避免无限循环并获取所有简单路径，您的 DFS 将需要维护一个visited集合，该集合按路径修改（一旦“发现”一个节点将其插入到集合中，一旦从堆栈中弹出，将其删除从集合）。
于 2012-12-30T10:21:18.110 回答
1
您可以调整 Dijkstra 的算法，另请参阅 A Recursive Algorithm to Find all Paths Between Two Gives Nodes
于 2012-12-30T13:31:30.350 回答