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

Question

我正在尝试开发一种算法，可以识别图中两个节点之间的所有可能路径，就像这个例子中的那样：

.

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

网络上只有关于深度优先搜索（DFS）、A*或Dijkstra的参考资料，但我认为它们在这种情况下不起作用。

有人知道如何解决吗？

- elias

---

作业？你已经尝试了什么？ - user85509

如果图是循环的，那么路径数量不会无限吗？ - jalf

@jalf，我也这么想，但维基百科说有些人意见不一。“没有重复顶点的路径称为简单路径，没有重复顶点或边（除了起始和结束顶点的必要重复）的循环称为简单循环。在现代图论中，通常隐含'简单'；即'循环'意味着'简单循环'，'路径'意味着'简单路径'，但这种约定并不总是被遵守，特别是在应用图论中。” - Doug McClean

Answer 1

你可以像|Vlad描述的那样使用DFS找到所有路径。要找出每条路径中出现的节点，你可以维护一个布尔数组，表示每个节点是否在每条路径中都出现过。当DFS找到一条路径时，遍历每个不在该路径中的顶点，并将相应的数组值设置为false。完成后，只有值为true的顶点才是每条路径中都出现的。

伪代码：

int source;
int sink;
int nVerts;
bool inAllPaths[nVerts]; // init to all true
bool visited[nVerts]; // init to all false
stack<int> 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) 的性能。

- Peter Alexander

Answer 2

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

• 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
  

如果您在注释中添加以n1...开头的行和n2...所在的行，则查询将返回所有图形中的所有路径。

- gaps96

Answer 3

针对这个问题，我首先会从目标节点 u 上进行 DFS，以获取形成树 t 的结果。然后，将所有位于以目标节点 v 为根的子树 s 中的节点着色，比如说涂成蓝色。

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
}

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

- Ryan

Answer 4

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

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

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

- IVlad

Answer 5

如果一个顶点从A到B的路径上是可达的，并且B也是从它可达的，则该顶点就在该路径上。

因此：从A开始进行泛洪填充。标记所有这些顶点。 从B开始进行泛洪填充，并按相反方向跟随边缘。你遇到的所有标记顶点都是解决方案的一部分。

- redtuna