数据结构实验图的遍历-2

一、需求分析以邻接表为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。以用户指定的节点为起点，分别输出每种遍历下的节点访问序列和相应的生成树的边集。二、概要设计1、图的邻接表存储表示1、边的结构定义typedefstructArcNode{邻接点的下标adjvex; 后继链指针*nextarc}ArcNode;2、顶点的结构类型定义typedefstructVNode{ 顶点信息data 指向第一条依附该顶点的弧的指针firstarc}VNode,存放点的邻接表AdjList[Maxnum];3、图的定义typedefstruct{ 邻接表vertices; 图的当前顶点数vexnum和弧数arcnum; 图的种类kind0-表示无向图，2-表示有向图}Graph;2、队列的链式存储结构1.链表节点类型定义typedefstructQNode{ 数据data; 下一个队员指针*next;}QNode,/指针数组Qnode2、链表定义typedefstruct{ 队头front; 队尾rear;}Queue;3、图的函数1、获取顶点的下标〔//返回顶点v在图中的位置函数〕intLocateVex(Graph&G,intv){ 遍历顶点顺序表得到顶点下标并返回；不到那么返回-1；}2、数组用于表示标志是否被访问boolVisited[Maxnum];4、队列函数1、构造一个空队列QintInitQueue(Queue&Q){构造一个空队列Q队头和队尾同指向一个地址；队头和队尾的next指向null; }2、插入队尾元素intEnQueue(Queue&Q,inte){插入元素e为Q的新的队尾元素;队尾元素的下一个元素为空；}3、队头出队intDeQueue(Queue&Q,int&e){队列不为空，那么删除Q的对头元素，用e返回其值； 释放队头元素的；}4、判断队列是否为空intQueueEmpty(QueueQ){队列为空返回1否那么返回0；}5、构造邻接表结构的图GvoidCreateGraph(Graph&G){用户输入选择图的类型；用户输入图的边数、顶点数；初始化顶点的信息和指向第一个顶点为空；用户输入边的信息；形成邻接链表的存储方式； 打印邻接链表；}6、深度优先遍历图-voidDFS(GraphG,intv){ 通过递归实现深度优先遍历}7、广度优先遍历图voidBFS(GraphG,intv){用队列来辅助实现广度的优先遍历；}8、深度优先遍历生成树voidDFSTraverse(Graph&G,intv){ 通过深度的优先遍历输出生成树的边集；}9、广度优先遍历生成树voidBFSTraverse(Graph&G,intv){ 用广度优先遍历输出广度优先遍历的生成树边集；}10、主函数intmain(){ 创立图； CreateGraph(G); 请输入访问的头顶点； 深度优先遍历图； DFS(G,u); 打印深度优先遍历图的生成树的边集； DFSTraverse(G,u); 广度优先遍历图 BFS(G,u); 打印广度优先遍历图的生成树的边集 BFSTraverse(G,u);}三、详细设计1、图的邻接表存储表示#defineMaxnum30//最大顶点数typedefstructArcNode{ intadjvex;//邻接点的下标 structArcNode*nextarc;//后继链指针}ArcNode;typedefstructVNode{ intdata;//顶点信息 ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[Maxnum];typedefstruct{ AdjListvertices;//邻接表 intvexnum,arcnum;//图的当前顶点数和弧数 intkind;//图的种类0-表示无向图，2-表示有向图}Graph;2、队列的链式存储结构typedefstructQNode{ intdata; structQNode*next;}QNode,*Qnode;//指针数组Qnodetypedefstruct{ Qnodefront; Qnoderear;}Queue;3、图的函数intLocateVex(Graph&G,intv){//返回顶点v在图中的位置函数 inti; for(i=0;i<G.vexnum;++i) if(G.vertices[i].data==v) break; else continue; if(i<G.vexnum) returni; else return-1;}boolVisited[Maxnum];4、队列函数//构造一个空队列QintInitQueue(Queue&Q){ Q.front=Q.rear=newQNode; if(!Q.front) return1; Q.front->next=NULL; return0;}//插入元素e为Q的新的队尾元素intEnQueue(Queue&Q,inte){ Qnodep=newQNode; if(!p) return1; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return0;}//队列不为空，那么删除Q的对头元素，用e返回其值intDeQueue(Queue&Q,int&e){ Qnodep; //if(Q.front==Q.rear) //return-1; p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; e=p->data; free(p); return1;}//判断是否队空intQueueEmpty(QueueQ){ if(Q.rear==Q.front) return1; else return0;}5、构造邻接表结构的图GvoidCreateGraph(Graph&G){ inti,j,k,v1,v2; ArcNode*p,*q; intv,m,kin; cout<<"请输入图的种类，0-表示无向图，2-表示有向图："; cin>>kin; cout<<"请输入顶点的个数："; cin>>v; cout<<"请输入边的条数："; cin>>m; G.vexnum=v; G.arcnum=m; G.kind=kin; for(k=0;k<G.vexnum;k++){ G.vertices[k].data=k+1;//每个顶点信息 G.vertices[k].firstarc=NULL;//初始化 } cout<<"请输入边,边的顶点用一个编号表示，全部n个顶点用1-n表示：\n"; for(k=0;k<G.arcnum;k++){ cout<<"请输入第"<<k+1<<"条边"; cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=newArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc;//头插法插入 G.vertices[i].firstarc=p; if(G.kind==0){//无向图 p=newArcNode; p->adjvex=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; } } cout<<"输入的图的邻接表如下：\n";//输出邻接表 for(k=0;k<G.vexnum;k++){ cout<<k<<""<<"v"<<G.vertices[k].data; q=G.vertices[k].firstarc; while(q->nextarc){ cout<<"->"<<(q->adjvex)+1; q=q->nextarc; } cout<<"->"<<(q->adjvex)+1<<"\n"; }}6、深度优先遍历图-voidDFS(GraphG,intv){ ArcNode*p; if(G.vertices[v].data==NULL)//注意输入v后，v要减1 cout<<"ERROR"; else{ if(Visited[v]==0){ //访问 cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) //未被访问 if(Visited[p->adjvex]==0) DFS(G,p->adjvex); } }}7、广度优先遍历图voidBFS(GraphG,intv){ inti; intw=0; ArcNode*p; QueueQ; //定义一个队列 if(G.vertices[v].data==NULL) cout<<"ERROR"; else{ for(i=0;i<G.vexnum;i++) Visited[i]=0;//初始化顶点，均未被访问过 InitQueue(Q);//初始化队列，构造一个空的队列 if(Visited[v]==0){ cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; EnQueue(Q,v);//第一个顶点入队 while(!QueueEmpty(Q)){ DeQueue(Q,w);//第一个顶点出队 for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc){ if(Visited[p->adjvex]==0){ cout<<"v"<<G.vertices[p->adjvex].data<<"->"; Visited[p->adjvex]=1; EnQueue(Q,p->adjvex); }//if }//for }//while }//if }}8、深度优先遍历生成树voidDFSTraverse(Graph&G,intv){ ArcNode*p; // if(Visited[v]==0){ Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) if(Visited[p->adjvex]==0){ cout<<"<"<<"v"<<G.vertices[v].data; cout<<","<<"v"<<G.vertices[p->adjvex].data<<">"<<","; DFSTraverse(G,p->adjvex); } }}9、广度优先遍历生成树voidBFSTraverse(Graph&G,intv){ inti; intw=0; ArcNode*p; QueueQ; //定义一个队列 if(G.vertices[v].data==NULL) cout<<"ERROR"; else{ for(i=0;i<G.vexnum;i++) Visited[i]=0;//初始化顶点，均未被访问过 InitQueue(Q);//初始化队列，构造一个空的队列 if(Visited[v]==0){ Visited[v]=1; EnQueue(Q,v);//第一个顶点入队 while(!QueueEmpty(Q)){ DeQueue(Q,w);//第一个顶点出队 for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc){ if(Visited[p->adjvex]==0){ cout<<"<"<<"v"<<G.vertices[w].data; cout<<","<<"v"<<G.vertices[p->adjvex].data<<">"<<","; Visited[p->adjvex]=1; EnQueue(Q,p->adjvex); }//if }//for }//while }//if }}10、主函数intmain(){ intu; GraphG; CreateGraph(G); cout<<"请输入访问的头顶点："; cin>>u; u=u-1; cout<<"深度优先遍历图的序列如下："<<endl;; DFS(G,u); cout<<endl; cout<<"深度优先遍历图的生成树的边集："<<endl<<"{"; for(inti=0;i<G.vexnum;i++) Visited[i]=0;//对图初始化，均未被访问过 DFSTraverse(G,u); cout<<"}"<<endl; cout<<"广度优先遍历图的序列如下："<<endl; BFS(G,u); cout<<endl; cout<<"广度优先遍历图的生成树的边集："<<endl<<"{"; for(intj=0;j<G.vexnum;j++) Visited[i]=0;//对图初始化，均未被访问过 BFSTraverse(G,u); cout<<"}"<<endl; return0;}四、调试分析原本是用多重链表的存储方式存储图，后来发现算法太复杂换而改用邻接链表存储；五、用户使用说明本程序的运行环境为MicrosoftVisualC++6.0。按提示键盘输入图的信息；接受其他命令后即执行相应运算和显示相应结果。关闭窗口那么退出程序。六、测试结果

七、源代码///////////////////////////////////////////////////////////用邻接表的存储方式存储图实现图的广度和深度的优先遍历//并输出每种遍历下的节点访问序列和相应生成树的边集///////////////////////////////////////////////////////#include<iostream>usingnamespacestd;//--------图的邻接表存储表示---------#defineMaxnum30//最大顶点数typedefstructArcNode{ intadjvex;//邻接点的下标 structArcNode*nextarc;//后继链指针}ArcNode;typedefstructVNode{ intdata;//顶点信息 ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[Maxnum];typedefstruct{ AdjListvertices;//邻接表 intvexnum,arcnum;//图的当前顶点数和弧数 intkind;//图的种类0-表示无向图，2-表示有向图}Graph;//--------------队列的链式存储结构-----------------typedefstructQNode{ intdata; structQNode*next;}QNode,*Qnode;//指针数组Qnodetypedefstruct{ Qnodefront; Qnoderear;}Queue;//***********图的函数******************intLocateVex(Graph&G,intv){//返回顶点v在图中的位置函数 inti; for(i=0;i<G.vexnum;++i) if(G.vertices[i].data==v) break; else continue; if(i<G.vexnum) returni; else return-1;}boolVisited[Maxnum];//*************队列函数***********************intInitQueue(Queue&Q){//构造一个空队列Q Q.front=Q.rear=newQNode; if(!Q.front) return1; Q.front->next=NULL; return0;}intEnQueue(Queue&Q,inte){//插入元素e为Q的新的队尾元素 Qnodep=newQNode; if(!p) return1; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return0;}intDeQueue(Queue&Q,int&e){//队列不为空，那么删除Q的对头元素，用e返回其值 Qnodep; //if(Q.front==Q.rear) //return-1; p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; e=p->data; free(p); return1;}intQueueEmpty(QueueQ){//判断是否队空 if(Q.rear==Q.front) return1; else return0;}//-----构造邻接表结构的图G------------voidCreateGraph(Graph&G){ inti,j,k,v1,v2; ArcNode*p,*q; intv,m,kin; cout<<"请输入图的种类，0-表示无向图，2-表示有向图："; cin>>kin; cout<<"请输入顶点的个数："; cin>>v; cout<<"请输入边的条数："; cin>>m; G.vexnum=v; G.arcnum=m; G.kind=kin; for(k=0;k<G.vexnum;k++){ G.vertices[k].data=k+1;//每个顶点信息 G.vertices[k].firstarc=NULL;//初始化 } cout<<"请输入边,边的顶点用一个编号表示，全部n个顶点用1-n表示：\n"; for(k=0;k<G.arcnum;k++){ cout<<"请输入第"<<k+1<<"条边"; cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=newArcNode; p->adjvex=j; p->nextarc=G.vertices[i].firstarc;//头插法插入 G.vertices[i].firstarc=p; if(G.kind==0){//无向图 p=newArcNode; p->adjvex=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; } } cout<<"输入的图的邻接表如下：\n";//输出邻接表 for(k=0;k<G.vexnum;k++){ cout<<k<<""<<"v"<<G.vertices[k].data; q=G.vertices[k].firstarc; while(q->nextarc){ cout<<"->"<<(q->adjvex)+1; q=q->nextarc; } cout<<"->"<<(q->adjvex)+1<<"\n"; }}//------------深度优先遍历图-------------------voidDFS(GraphG,intv){ ArcNode*p; if(G.vertices[v].data==NULL)//注意输入v后，v要减1 cout<<"ERROR"; else{ if(Visited[v]==0){ //访问 cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) //未被访问 if(Visited[p->adjvex]==0) DFS(G,p->adjvex); } }}//--------------广度优先遍历图-----------------voidBFS(GraphG,intv){ inti; intw=0; ArcNode*p; QueueQ; //定义一个队列 if(G.vertices[v].data==NULL) cout<<"ERROR"; else{ for(i=0;i<G.vexnum;i++) Visited[i]=0;//初始化顶点，均未被访问过 InitQueue(Q);//初始化队列，构造一个空的队列 if(Visited[v]==0){ cout<<"v"<<G.vertices[v].data<<"->"; Visited[v]=1; EnQueue(Q,v);//第一个顶点入队 while(!QueueEmpty(Q)){ DeQueue(Q,w);//第一个顶点出队 for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc){ if(Visited[p->adjvex]==0){ cout<<"v"<<G.vertices[p->adjvex].data<<"->"; Visited[p->adjvex]=1; EnQueue(Q,p->adjvex); }//if }//for }//while }//if }}//*************深度优先遍历生成树********************voidDFSTraverse(Graph&G,intv){ ArcNode*p; if(Visited[v]==0){ Visited[v]=1; for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc) if(Visited[p->adjvex]==0){ cout<<"<"<<"v"<<G.vertices[v].data; cout<<","<<"v"<<G.vertices[p->adjvex].data<<">"<<","; DFSTraverse(G,p->adjvex); } }}//*************广度优先遍历生成树**************