循环无向图中的所有可能路径

我正在尝试开发一种算法来识别图中两个节点之间的所有可能路径，如下例所示：

。

实际上，我只需要知道哪些节点出现在所有现有路径中。

在网络上只有关于DFS，A *或dijkstra的参考，但我认为它们在这种情况下不起作用。

有谁知道如何解决它？

Answer 1

您可以使用DFS找到所有路径，如| Vlad描述的。 要找到每个路径中出现的节点，您可以只维护一个布尔数组，说明到目前为止每个节点是否都出现在每个路径中。 当您的DFS找到路径时，请遍历不在路径中的每个顶点，并将相应的数组值设置为false。 完成后，只有值为true的顶点才会出现在每个路径中。

伪代码：

int source; int sink; int nVerts; bool inAllPaths[nVerts]; // init to all true bool visited[nVerts]; // init to all false stack path; // init empty bool dfs(int u) if (visited[u]) return; if (u == sink) for i = 0 to nVerts-1 if !stack.contains(i) inAllPaths[i] = false; return true; else visited[u] = true; stack.push(u); foreach edge (u, v) dfs(v); stack.pop(); visited[u] = false; return false; main() dfs(source); // inAllPaths contains true at vertices that exist in all paths // from source to sink. 

但是，这种算法效率不高。 例如，在n个顶点的完整图形中（所有顶点都具有与所有其他顶点的边缘），路径的数量将为n！ （n阶乘）。

更好的算法是分别检查每个顶点的每个路径中是否存在。 对于每个顶点，尝试找到从源到接收器的路径，而不必去往该顶点。 如果你找不到一个，那是因为顶点出现在每个路径中。

伪代码：

 // Using the same initialisation as above, but with a slight modification // to dfs: change the foreach loop to foreach edge (u, v) if (dfs(v)) return true; // exit as soon as we find a path main() for i = 0 to nVerts-1 set all visited to false; if (inAllPaths[i]) visited[i] = true; if (dfs(source)) inAllPaths[i] = false; visited[i] = false; 

不幸的是，在搜索路径时，这仍然是指数最坏的情况。 您可以通过将搜索更改为广度优先搜索来解决此问题。 如果我没弄错的话，这应该会给你O（VE）表现。

Answer 2

从起始节点运行DFS并保留自己的堆栈，告诉您在任何给定时间看到的节点。 注意循环：当你看到一个节点两次时，你有一个循环，你必须中止你当前的路径。 注意不要访问节点的父节点，以避免长度为1的循环（向DFS函数添加parent参数，这将有所帮助）。

然后，当您到达目标节点时，输出堆栈的内容。

DFS完成后，您将拥有所有路径。

Answer 3

对于这个问题，我首先会得到一个由目标节点u上的DFS组成的树。 然后，为以第二个目标节点v为根的子树中的所有节点（例如蓝色）着色。

 For each node k in subtree s, if k has an edge to a non-blue node x then k is true and x is true. 

另外，将v标记为true。 最后，我会使用递归函数到叶子。 就像是

 function(node n){ if(n = null) return false if(function(n.left) or function(n.right) or n.val){ n.val = true return true } else return false } 

标记为true的所有节点将是从u到v的路径中的节点。运行时最多（顶点+边缘），因为DFS =（V + E）最多for循环（V）最多递归（V）

Answer 4

我知道它已经有一段时间了，但是我来到这里寻找一些算法来查找SQL或Java中的All Paths（不仅是最短路径）而且我发现了这三个（我只是发布它们以保持概念组织）：

• Java的

  http://introcs.cs.princeton.edu/java/45graph/AllPaths.java.html （依赖关系：Graph，ST，Set，In，位于http://introcs.cs.princeton.edu/java/45graph / ）

• SQL（PostgreSQL）。

  检查WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS

  http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/

• PL / SQL（Oracle）

  https://forums.oracle.com/forums/thread.jspa?threadID=2415733

   select pth as "Path", distance as "Distance" from ( select connect_by_root(n1) || sys_connect_by_path(n2,'>') pth ,n2, level as distance from -- Edge List Table (select 'A' n1,'B' n2 from dual union all select 'A','C' from dual union all select 'B','C' from dual union all select 'B','D' from dual union all select 'D','G' from dual union all select 'C','G' from dual union all select 'D','I' from dual union all select 'C','E' from dual union all select 'E','F' from dual union all select 'F','G' from dual union all select 'F','H' from dual ) links start with n1='A' connect by nocycle prior n2=n1) where n2 = 'G'; 

  结果：

   Distance Path 3 A>B>C>G 5 A>B>C>E>F>G 3 A>B>D>G 2 A>C>G 4 A>C>E>F>G 

如果您放入注释，则行start with n1... where n2...查询将返回所有图形中的所有路径。

Answer 5

如果顶点位于从A到B的路径上，如果它可以从A到达，则B可以从它到达。

所以：从A开始进行洪水填充。标记所有这些顶点。 从B开始进行洪水填充，然后反向跟随边缘。 您遇到的所有标记顶点都是解决方案的一部分。