1

是否有可能使用堆栈的 DFS 实现，它为我提供了在图形（循环/非循环）的情况下从一个顶点到另一个顶点的所有可能路径。

我目前的 DFS 代码如下：-

void Graph::DFS(int x, int required){
stack s;
bool *visited = new bool[n+1];
int i;
for(i = 0; i <= n; i++)
    visited[i] = false;
s.push(x);
visited[x] = true;
if(x == required) return;
cout << "Depth first Search starting from vertex ";
cout << x << " : " << endl;
while(!s.isEmpty())
{
    int k = s.pop();
    if(k == required)
    {
      cout<<k<<" ";
      break;
    }
    cout<<k<<" ";
    for (i = n; i >= 0 ; --i)
        if (isConnected(k, i) && !visited[i]) 
        {
            s.push(i);
            visited[i] = true;
        }
}
  cout<<endl;
  delete [] visited;
 }

如果存在的话，这确实给了我一条可能的路径，但我想要的是all possible paths而不仅仅是一个。

4

1 回答 1

2

不——在无向图的情况下，有无限数量的路径（只需在任何给定的边上来回走动，或绕过循环），因此您不能编写代码来将它们全部返回。

如果您对其他一些限制（例如“仅访问每个节点一次的路径”）进行一些限制，那么可以。

对于“只访问每个节点一次的路径”的约束，您将基本上更改您的搜索，以便visited[i] 是“我在这条路径上访问过[i] 这个”而不是“我曾经访问过这个节点吗？” （就像现在在代码中一样），然后每次到达目标时，都应该将当前路径添加到找到的路径列表中，并像没有找到它一样继续。

于 2012-08-19T07:26:14.963 回答