图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v，w|v，wv且P(v，w)，v，w表示从v到w得弧，谓词P(v，w)定义了弧v，w的意义或信息}}ADTGraph2.此抽象数据类型中的一些常量如下：#defineTRUE1#defineFALSE0#defineOK1#definemax_n20//最大顶点数typedefcharVertexType[20];typedefenum{DG,DN,AG,AN}GraphKind;enumBOOL{False,True};3.树的结构体类型如下所示：typedefstruct{//弧结点与矩阵的类型intadj;//VRType为弧的类型。图--0,1;网--权值int*Info;//与弧相关的信息的指针,可省略}ArcCell,AdjMatrix[max_n][max_n];typedefstruct{VertexTypevexs[max_n];//顶点AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//顶点数，边数}MGraph;//队列的类型定义typedefintQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;4.本程序包含三个模块1).主程序模块voidmain(){创建树；深度优先搜索遍历；广度优先搜索遍历；}2).树模块——实现树的抽象数据类型3).遍历模块——实现树的深度优先遍历和广度优先遍历各模块之间的调用关系如下：主程序模块树模块遍历模块三.详细设计#includestdafx.h#includeiostreamusingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#definemax_n20//最大顶点数typedefcharVertexType[20];typedefenum{DG,DN,AG,AN}GraphKind;enumBOOL{False,True};typedefstruct{//弧结点与矩阵的类型intadj;//VRType为弧的类型。图--0,1;网--权值int*Info;//与弧相关的信息的指针,可省略}ArcCell,AdjMatrix[max_n][max_n];typedefstruct{VertexTypevexs[max_n];//顶点AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//顶点数，边数}MGraph;//队列的类型定义typedefintQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//初始化队列intInitQueue(LinkQueue*Q){returnOK;}//判断队列是否为空intEmptyQueue(LinkQueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}//入队列intEnQueue(LinkQueue*Q,QElemTypee){QueuePtrp;p-data=e;p-next=NULL;(*Q).rear-next=p;(*Q).rear=p;returnOK;}//出队列intDeQueue(LinkQueue*Q,QElemType*e){QueuePtrp;if((*Q).front==(*Q).rear)return-1;p=(*Q).front-next;*e=p-data;(*Q).front-next=p-next;if((*Q).rear==p)(*Q).rear=(*Q).front;deletep;returnOK;}/*顶点在顶点向量中的定位*/intLocate(MGraphG,VertexTypev){inti;for(i=0;iG.vexnum;i++)if(strcmp(v,G.vexs[i])==0)break;returni;}voidCreateGraph(MGraph&G){//图G用邻接矩阵表示,创建图intk,i,j;VertexTypevi,vj;cout请输入图的顶点个数和边的数目:;cinG.vexnumG.arcnum;cout请输入顶点:;for(k=0;kG.vexnum;k++)cinG.vexs[k];for(i=0;iG.vexnum;i++)//初始化邻接矩阵for(j=0;jG.vexnum;j++)G.arcs[i][j].adj=0;cout请输入边集:endl;for(k=0;kG.arcnum;k++){cinvivj;i=Locate(G,vi);j=Locate(G,vj);//求Vi和Vj的下标G.arcs[i][j].adj=1;G.arcs[j][i].adj=1;}}intFirstAdjVex(MGraphG,intV){//图G用邻接矩阵表示，求下标为V的顶点的第一个邻接点inti=0;while(iG.vexnum&&G.arcs[V][i].adj==0){i++;}if(i=G.vexnum)return-1;elsereturni;//返回V的第一个邻接点的下标}intNextAdjVex(MGraphG,intV,intw){//图G用邻接矩阵表示inti=w+1;while(iG.vexnum&&G.arcs[V][i].adj==0)i++;if(i=G.vexnum)return-1;//V的w邻接点之后没有邻接点elsereturni;//返回V行w列之后第一个非0元的下标}intvisited[100];/*设置全局的访问标志数组*/voidDFS(MGraphG,intv){//从序号为v的顶点出发，对图G做一次深度优先搜索遍历intw;visited[v]=1;coutG.vexs[v];for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){if(!visited[w])DFS(G,w);}}//深度优先搜索遍历图GvoidDFSTraverse(MGraphG){intv;for(v=0;vG.vexnum;v++)visited[v]=0;for(v=0;vG.vexnum;v++)if(!visited[v])DFS(G,v);//若顶点v未被访问，从v开始遍历}voidBFSTraverse(MGraphG){intv,w,u;LinkQueueQ;for(v=0;vG.vexnum;++v)visited[v]=0;InitQueue(&Q);//初始化队列for(v=0;vG.vexnum;++v){if(!visited[v]){visited[v]=1;coutG.vexs[v];EnQueue(&Q,v);//v入队while(!EmptyQueue(Q)){DeQueue(&Q,&u);//队头元素u出队for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)){if(!visited[w]){visited[w]=1;coutG.vexs[w];EnQueue(&Q,w);}}}}}}intmain(){MGraphG;CreateGraph(G);cout深度优先搜索遍历顺序为:;DFSTraverse(G);coutendl;cout广度优先搜索遍历序列为:;BFSTraverse(G);coutendl;return0;}四.调试分析1.先建立一幅图，然后依次进行深度优搜索先遍历。2.利用队列来实现广度优先搜索遍历。五.用户手册1．本程序的运行环境为Win7操作系统，执行文件为：Debug/图的遍历.exe2．进入演示程序后，即现实文本方式的用户界面：六.测试结果依次输入数据