tu.rar_tu_图的遍历

#include<iostream.h> #include<stdio.h> #include"tutu.h" void Check(int n,int& i,int& j); void InitGAdjoin(adjlist&GL,int n)//初始化图的邻接表 { GL=new edgenode*[n]; for(int i=1;i<=n;i++)GL[i]=NULL; } void CreateAdjoin(adjlist &GL,int n,int m)//建立图的邻接表 { int i,j,k,e; cout<<"输入图的总边数："; cin>>e; if(m==0){ //建立无向图 for(k=0;k<e;k++){ cout<<"输入第"<<k<<"条边的起点和终点序号！"<<endl; cin>>i>>j; Check(n,i,j); edgenode*p=new edgenode; p->adjvex=j; p->next=GL[i]; GL[i]=p; //向序号为i的单链表的表头插入一个边结点 p=new edgenode; p->adjvex=i; p->next=GL[j]; GL[j]=p; //向序号为j的单链表的表头插入一个边结点 } cout<<endl<<"=============="<<endl; cout<<"图的邻接表为:"<<endl; for(i=1;i<=n;i++){ edgenode*p=GL[i]; cout<<i-1<<" |"<<"V"<<i; for(p=GL[i];p!=NULL;p=p->next) cout<<"|-|->|"<<p->adjvex; cout<<"|^|"; cout<<endl; } //输出邻接表 } else if(m==1){//建立有向图 for(k=1;k<=e;k++){ cout<<"输入第"<<k<<"条边的起点和终点序号！"<<endl; cin>>i>>j; Check(n,i,j); //向序号为i的表头插入一个边结点 edgenode*p=new edgenode; p->adjvex=j; p->next=GL[i]; GL[i]=p; } cout<<"图的邻接表为:"<<endl; for(i=1;i<=n;i++){ edgenode*p=GL[i]; cout<<i-1<<" |"<<"V"<<i; for(p=GL[i];p!=NULL;p=p->next) cout<<"|-|->|"<<p->adjvex; cout<<"|^|"; cout<<endl; } //输出邻接表 } } void dfsAdjoin(adjlist GL,bool*& visited,int i,int n) //从初始点出发深度优先搜索邻接表 GL表示的图 { cout<<i<<' '; visited[i]=true; edgenode* p=GL[i]; while(p!=NULL){ int j=p->adjvex; //j为Vi的一个邻接点的序号 if(!visited[j]) dfsAdjoin(GL,visited,j,n); p=p->next; //使p指向Vi单链表的下一个边结点 } } void bfsAdjoin(adjlist GL,bool*& visited,int i,int n) //从初始点出发广度优先搜索邻接表 GL表示的图 { const int MaxLength=30; int q[MaxLength]={0}; //定义一个队列q,其元素类型为整形 int front=0,rear=0; //定义队首和队尾指针 cout<<i<<' '; //访问Vi visited[i]=true; //标记初始点Vi已访问过 q[++rear]=i; //将已访问过的初始点序号i入队 while(front!=rear){ //当队列非空时进行循环处理 front=(front+1)%MaxLength; //删除队首元素，第一次执行时k的值为i int k=q[front]; edgenode* p=GL[k]; //取Vk邻接表的表头指针 while(p!=NULL){ //依次搜索Vk的每一个结点 int j=p->adjvex; //Vj为Vk的一个邻接点 if(!visited[j]){ //若Vj没有被访问过则进行处理 cout<<j<<' '; visited[j]=true; rear=(rear+1)%MaxLength; q[rear]=j; } p=p->next; } } } void Check(int n,int & i,int & j) //检查输入的边序号是否越界，若越界则重输 { while(1){ if(i<=0||i>n||j<=0||j>n) cout<<"输入有误,请重新输入！"; else return; cin>>i>>j; } } #include<iostream.h> #include"tutu.h" void main() { int i,n,m; cout<<"=============="<<endl; cout<<"输入图的顶点数:"; cin>>n; cout<<"输入是否有向（0为无，1为有）:"; cin>>m; bool*visited=new bool[n]; adjlist gl; InitGAdjoin(gl,n); CreateAdjoin(gl,n,m); cout<<"=============="<<endl; cout<<"图的深度优先遍历序列:"<<endl; for(i=1;i<=n;i++)visited[i]=false; dfsAdjoin(gl,visited,1,n); cout<<endl<<"=============="<<endl; cout<<"图的广度优先遍历序列:"<<endl; for(i=1;i<=n;i++)visited[i]=false; bfsAdjoin(gl,visited,1,n); cout<<endl; }