关于c++图的遍历(代码)
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<cstring> const int maxsize=100; const int vertexnum=20; typedef struct{ int *qbase; int front,rear; }sqqueue; void initqueue(sqqueue &q){ q.qbase = (int *)malloc(sizeof(int) *vertexnum); if(!q.qbase) return ; q.rear = q.front = -1; } void enqueue(sqqueue &q, int i){ q.qbase[q.rear ++] = i; } void dequeue(sqqueue &q, int &i){ i = q.qbase[q.front ++]; } int queueempty(sqqueue q){ if(q.front == q.rear) return 1; return 0; } template<class t> class mgraph { public: mgraph(t a[],int n,int e); ~mgraph(){} void dfstraverse(); void bfstraverse(int v); void deeptra(int v[],int n); private: t vertex[maxsize]; //节点数组 int arc[maxsize][maxsize]; //矩阵 int vertexnum,arcnum; //节点数与边数 int visited[maxsize]; //访问记录 }; template<class t> mgraph<t>::mgraph(t a[],int n,int e) { int i,j; vertexnum=n; arcnum=e; for(i=0;i<vertexnum;i++) { vertex[i]=a[i]; } for(i=0;i<vertexnum;i++) for(j=0;j<vertexnum;j++) { arc[i][j]=0; } for(int k=0;k<arcnum;k++) { std::cout<<"输入第"<<k+1<<"条边:"<<std::endl; std::cin>>i>>j; arc[i][j]=1; arc[j][i]=1; } } template<class t> void mgraph<t>::dfstraverse() { int i; for(i=0;i<vertexnum;i++) { visited[i]=0; } std::cout<<"深度优先遍历:"<<std::endl; for(i=0;i<vertexnum;i++) { if(visited[i]==0) deeptra(visited,0); } } template<class t> void mgraph<t>::deeptra(int v[],int n) { int i; visited[n]=1; std::cout<<vertex[n]; for(i=0;i<vertexnum;i++) { if(arc[n][i]!=0&&visited[i]==0) { deeptra(visited,i); } } } template<class t> void mgraph<t>::bfstraverse(int v) { sqqueue q; q.front=q.rear=-1; int i; for(i=0;i<vertexnum;i++) { visited[i]=0; } std::cout<<std::endl; std::cout<<"广度优先遍历:"<<std::endl; std::cout<<vertex[v]; visited[v]=1; initqueue(q); enqueue(q,v); while(!queueempty(q)) { dequeue(q,v); for(int i=0;i<vertexnum;i++) if(arc[v][i]==1&&visited[i]==0) { std::cout<<vertex[i]; visited[i]=1; enqueue(q,i); } } } int main() { int e,n; std::cout<<"点的个数:"<<" "; std::cin>>e; std::cout<<"边的个数:"<<" "; std::cin>>n; char s[e]; for(int i=0;i<e;i++) { std::cout<<"输入第"<<i+1<<"个点:"; std::cin>>s[i]; } mgraph<char> m(s,e,n); m.dfstraverse(); m.bfstraverse(0); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607552.html