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

Question

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

.

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

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

有人知道怎么解决吗？

Answer 1

您可以像 |Vlad 描述的那样使用 DFS 找到所有路径。要找到哪些节点出现在每条路径中，您可以只维护一个 boolean 值数组，说明每个节点到目前为止是否已经出现在每条路径中。当你的 DFS 找到路径时，遍历路径中的每个顶点 not 并将相应的数组值设置为 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) 性能。