上篇深度优先遍历（DFS）的时候，在二维矩阵中，把标识放在了side上，在上面还感觉没有啥子影响，但由于广度遍历的时候，标记的设置要放在push到queue中的时候，就比较难受，所以最好还是把访问标识放在vertex中。广度优先遍历（BFS）借助stl deque实现，借用上篇的代码修改实现，还是采用二维矩阵和邻接表实现
#include<iostream> #include<deque> #define MAX_VERTEX 100 using namespace std; deque<int> _deque; //array struct Side_Array{ int link; }; struct Vertex_array{ int mark; char data; }; Vertex_array vertex_infos[MAX_VERTEX]; Side_Array matrix[MAX_VERTEX][MAX_VERTEX]; void BFS_For_Array(int x){ if(vertex_infos[x].data==0){ return; } cout<<vertex_infos[x].data; for(int i=0;i<MAX_VERTEX;i++){ if(matrix[x][i].link==1&&vertex_infos[i].mark==0){ _deque.push_back(i); vertex_infos[i].mark=1; } } while(!_deque.empty()){ int index=_deque.front(); _deque.pop_front(); BFS_For_Array(index); } } int Array_Check(){ for(int i=0;i<MAX_VERTEX;i++){ if(vertex_infos[i].mark==0&&vertex_infos[i].data!=0){ return i; } } return -1; } //list struct Side{ int index; int weight; Side* next; }; struct Vertex{ char data; int mark; Side* first; }; typedef Vertex AdjList[MAX_VERTEX]; struct AdjGraph { AdjList adjlist; int num_vertex; int num_side; }; void BFS_For_List(AdjGraph& adjGraph,int x){ if(adjGraph.adjlist[x].data==0){ return; } cout<<adjGraph.adjlist[x].data; Side* p=adjGraph.adjlist[x].first; while(p!=0){ if(adjGraph.adjlist[p->index].mark==0){ _deque.push_back(p->index); adjGraph.adjlist[p->index].mark=1; } p=p->next; } while(!_deque.empty()){ int index=_deque.front(); _deque.pop_front(); BFS_For_List(adjGraph,index); } } int List_Check(AdjGraph& adjGraph){ for(int i=0;i<MAX_VERTEX;i++){ if(adjGraph.adjlist[i].mark==0&&adjGraph.adjlist[i].data!=0){ return i; } } return -1; } int main(){ //array /* for(int i=0;i<MAX_VERTEX;i++){ vertex_infos[i].data=0; vertex_infos[i].mark=0; for(int j=0;j<MAX_VERTEX;j++){ matrix[i][j].link=0; } } cout<<"input vertex and side nums:"; int num_vertex; int num_side; cin>>num_vertex>>num_side; cout<<"input vertex char data:"; for(int i=0;i<num_vertex;i++){ cin>>vertex_infos[i].data; } for(int i=0;i<num_side;i++){ int v1; int v2; cout<<"input two vertex:"; cin>>v1>>v2; matrix[v1][v2].link=1; matrix[v2][v1].link=1; } int index=Array_Check(); vertex_infos[0].mark=1; while(index!=-1){ BFS_For_Array(index); index=Array_Check(); } cout<<endl;*/ //list AdjGraph adjGraph; for(int i=0;i<MAX_VERTEX;i++){ adjGraph.adjlist[i].mark=0; adjGraph.adjlist[i].data=0; adjGraph.adjlist[i].first=0; } cout<<"input vertex and side nums:"; cin>>adjGraph.num_vertex>>adjGraph.num_side; cout<<"input vertex char data:"; for(int i=0;i<adjGraph.num_vertex;i++){ cin>>adjGraph.adjlist[i].data; } for(int i=0;i<adjGraph.num_side;i++){ int v1; int v2; cout<<"input two vertex:"; cin>>v1>>v2; Side* side1=new Side(); side1->index=v2; Side* side2=new Side(); side2->index=v1; if(adjGraph.adjlist[v1].first==0){ adjGraph.adjlist[v1].first=side1; } else{ Side* temp=adjGraph.adjlist[v1].first; adjGraph.adjlist[v1].first=side1; side1->next=temp; } if(adjGraph.adjlist[v2].first==0){ adjGraph.adjlist[v2].first=side2; } else{ Side* temp=adjGraph.adjlist[v2].first; adjGraph.adjlist[v2].first=side2; side2->next=temp; } } int index=List_Check(adjGraph); adjGraph.adjlist[0].mark=1; while(index!=-1){ BFS_For_List(adjGraph,index); index=List_Check(adjGraph); } cout<<endl; for(int i=0;i<adjGraph.num_vertex;i++){ Side* p=adjGraph.adjlist[i].first; while(p!=0){ Side* temp=p->next; delete p; p=temp; } } return 0; }
