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

Question

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

.

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

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

有谁知道如何解决它？

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) 的性能。