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;
}

我的问题是它使用队列而不是堆栈,所以它是正确的吗？当我应该输入图形时,它应该像相邻矩阵还是？请帮助我,这个算法使用默认值,那么我该如何改变呢？

Answer 1

有趣.我找到了您所指的代码http://www.koders.com/cpp/fid1107E4F79ED191B482853E3206A2F13FC77B4310.aspx.

当然,它使用queue标准C++库中的类,因此实现了广度优先的搜索算法.使用C++堆栈应该为您提供所需的深度优先搜索.

去表明你不能相信你在互联网上看到的一切(甚至包括这个答案).:-)

至于你的第二个问题,这个发布的代码确实使用了邻接矩阵.实际上,您甚至可以更精确地说,通过检查代码,它正在实现没有平行边的无向图.

附录

代码在行动,显示它是BFS:http://ideone.com/mLl23