专题--深度优先搜索与广度优先搜索

 1 #include <iostream> 2 #include <queue> 3 using namespace std; 4  5 typedef char VertexType; 6 typedef int EdgeType; 7 const int MAXVEX=100; 8 const int INFINITY=65535; 9 10 struct MGraph11 {12     VertexType vexs[MAXVEX];      //顶点表13     EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看做边表14     int numVertexes,numEdges;     //图中当前的顶点数和边数15 };16 17 //深度优先18 void DFS(MGraph,int);  //函数前置声明19 bool visited[MAXVEX];20 void DFSTraverse(MGraph G)21 {22     for(int i=0;i<G.numVertexes;++i)23         visited[i]=false;24     for(int i=0;i<G.numVertexes;++i)25         if(!visited[i])26             DFS(G,i);   //若是连通图，只会执行一次27 }28 void DFS(MGraph G,int i)29 {30     visited[i]=true;31     cout<<G.vexs[i]<<endl;32 33     for(int j=0;j<G.numVertexes;++j)34         if(G.arc[i][j]==1&&!visited[j])  //有连接且还未访问35             DFS(G,j);    //递归调用36 }37 //广度优先38 void BFSTraverse(MGraph G)39 {40     for(int i=0;i<G.numVertexes;++i)41         visited[i]=false;42     queue<int> Q;  //申请一个辅助队列43     for(int i=0;i<G.numVertexes;++i)44     {45         visited[i]=true;46         cout<<G.vexs[i]<<endl;47 48         Q.push(i); //入队列49         while(!Q.empty())50         {51             int i=Q.front(); //取出首元素52             Q.pop();   //删除队列首元素53             for(int j=0;j<G.numVertexes;++j)54             {55                 if(G.arc[i][j]==1&&!visited[j])56                 {57                     visited[j]=true;58                     Q.push(j);   //入队列59                 }60             }61         }62     }63 64 }