在循环无向图中所有可能的路径 [英] All possible paths in a cyclic undirected graph

问题描述

我试图开发一种算法，识别两个节点之间的所有可能路径的图，在这个例子：

I'm trying to develop an algorithm that identifies all possible paths between two nodes in a graph, as in this example:

。

.

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

in fact, i just need to know which nodes appear in all existing paths.

在网络只得到了有关DFS，A *或Dijkstra算法引用，但我认为他们不会在这种情况下工作。

in the web only got references about DFS, A* or dijkstra, but i think they doesn't work in this case.

有谁知道如何解决呢？

推荐答案

您可以找到使用类似于DFS的所有路径|弗拉德描述。要找到哪些节点出现在每个路径，你可以只维持布尔数组，表示每个节点是否已经出现在每一条路径为止。当你的DFS找到一条路径，通过路径中的每个顶点的没有的和相应的数组值设置为false。当您完成，只有具有真正价值的顶点将出现在每一个路径的人。

You can find all paths using DFS like |Vlad described. To find which nodes appear in every path, you could just maintain an array of booleans that says whether each node has appeared in every path so far. When your DFS finds a path, go through each vertex not in the path and set the corresponding array value to false. When you are done, only the vertices with values of true will be the ones that appear in every path.

伪code：

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个因子）。

However, this algorithm isn't very efficient. For example, in a complete graph of n vertices (all vertices have edges to all others) the number of paths will be n! (n factorial).

有一个更好的算法是将在每个顶点的每个路径单独检查是否存在。对于每一个顶点，试图找到从源到接收器的路径，而无需到顶点。如果你不能找到一个，那是因为顶点将出现在每一条路径。

A better algorithm would be to check for the existence in every path of each vertex separately. For each vertex, try to find a path from the source to the sink without going to that vertex. If you can't find one, that's because the vertex appears in every path.

伪code：

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

Unfortunately, this still has exponential worst case when searching for a path. You can fix this by changing the search to a breadth-first search. If I'm not mistaken, this should give you O(VE) performance.

这篇关于在循环无向图中所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！