查找两个节点之间所有路径的高效算法

Question

我目前正在研究递归 DFS，以检索无向且未加权图中两个节点之间的所有路径。它递归地获取起始节点和结束节点，以及该节点及其相邻节点上的DFS，同时保存路径。我想知道是否有更有效的方法来找到所有路径？

Answer 1

简单路径的数量呈指数级增长，DFS 基本上将所有路径创建为 0，因此您的方法是正确的，尽管很耗时（但这是问题本身的一部分，而不是算法）。

您也许可以通过从图形中消除不通向目标的节点（如果存在此类节点）来对其进行一些优化 - 在计算它们之前有效地修剪不成功的搜索。

请注意，如果图形包含循环 - 可能会有无限数量的路径（尽管简单路径的数量有限）。请注意，为了避免无限循环并获取所有简单路径，您的 DFS 将需要维护一个visited集合，该集合针对每个路径进行修改（一旦“发现”节点将其插入到集合中，一旦从堆栈中弹出，请将其删除从集合）。