DFS算法使用队列吗？

Question

我在互联网上看到了以下DFS算法：

#include<iostream>
#include<queue>
#define MAX 100

using namespace std;

queue<int> myQueue;
int G[MAX][MAX];
int visit[MAX];
int V, E;


void dfs(int s) {
     int i, j, node;
     memset(visit, 0, sizeof(visit));
     myQueue.push(s);

     while(!myQueue.empty())
     {
          node = myQueue.front();
          myQueue.pop();
          if(visit[node]) continue;
          visit[node] = 1;
          cout << node << " ";

          for(i=0; i<V; i++)
               if(G[i][node]) myQueue.push(i);
          for(j=0; j<V; j++)
               if(G[node][j]) myQueue.push(j);     
     }

}

int main() {
    memset(visit, 0, sizeof(visit));
    dfs(0);
    return 0;
}

我的问题是它使用队列而不是栈，这样正确吗？当我输入图时，应该是邻接矩阵还是？请帮帮我。此算法使用默认值，我该如何更改？

- user466534

Answer 1

有趣。我找到了你提到的代码 http://www.koders.com/cpp/fid1107E4F79ED191B482853E3206A2F13FC77B4310.aspx。

可以肯定地说，它使用了标准 C++ 库中的 queue 类，并因此实现了一个广度优先搜索算法。使用C++ 栈应该可以给你想要的深度优先搜索。

这说明你不能相信互联网上看到的一切（也许包括这个答案）。 ：-）

至于你的第二个问题，这个发布的代码确实使用了邻接矩阵。事实上，通过检查代码，你甚至可以更精确地说它实现了一个无平行边的无向图。

补充说明

演示代码，显示它是一个 BFS：http://ideone.com/mLl23

- Ray Toal

---

所以，如果我使用堆栈而不是队列，它会正确吗？图应该解释为邻接矩阵，对吗？ - user466534

是的和是的。添加到答案中。 - Ray Toal

@dato 我已经证明了这确实是一个广度优先搜索算法。请参见http://ideone.com/mLl23。输出显示0 1 3 2，显然是BFS。如果它是DFS，那么输出应该是0 1 2 3。希望这对你有用。尝试使用一个堆栈来执行它，并看看效果如何。 :-) - Ray Toal