数据结构实验四图的深度优先与广度优先遍历

第1页共4页天津理工大学实验报告学院（系）名称：计算机与通信工程学院姓名学号专业计算机科学与技术班级2009级1班实验项目实验四图的深度优先与广度优先遍历课程名称数据结构与算法课程代码实验时间2011年5月12日第5-8节实验地点7号楼215批改意见成绩教师签字：实验四图的深度优先与广度优先遍历实验时间：2011年5月12日，12:50-15:50（地点：7-215）实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。具体实验题目：（任课教师根据实验大纲自己指定）每位同学按下述要求实现相应算法：根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph():按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图实验报告格式及要求：按学校印刷的实验报告模版书写。（具体要求见四）第2页共4页实验思路：首先，定义邻接矩阵和图的类型，定义循环队列来存储，本程序中只给出了有向图的两种遍历，定义深度优先搜索和广度优先搜索的函数，和一些必要的函数，下面的程序中会有说明，然后是函数及运行结果！#includeiostream#includecstdlibusingnamespacestd;#defineMAX_VERTEX_NUM20//最大顶点数#defineMaxSize100boolvisited[MAX_VERTEX_NUM];enumGraphKind{AG,AN,DG,DN};//图的种类，无向图，无向网络，有向图，有向网络structArcNode{intadjvex;ArcNode*nextarc;};structVNode{intdata;ArcNode*firstarc;};structGraph{VNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的类型};structSeqQueue{int*base;intfront,rear;};SeqQueueInitQueue(){//循环队列初始化SeqQueueQ;Q.base=newint;Q.front=0;Q.rear=0;returnQ;}voidDeQueue(SeqQueue&Q,int&u){//出队操作u=*(Q.base+Q.front);Q.front=(Q.front+1)%MaxSize;}intQueueFull(SeqQueueQ){//判断循环队列是否满return(Q.front==(Q.rear+1)%MaxSize)?1:0;}第3页共4页voidEnQueue(SeqQueue&Q,intx){//入队操作if(QueueFull(Q)){cout队满，入队操作失败！endl;exit(0);}*(Q.base+Q.rear)=x;Q.rear=(Q.rear+1)%MaxSize;}voidCreateDG(Graph&G,intn,inte){//初始化邻接表头结点intj;for(inti=0;in;++i){G.vertex[i].data=i;G.vertex[i].firstarc=NULL;}for(i=0;ie;++i){cinij;//输入边的信息ArcNode*s;s=newArcNode;s-adjvex=j;s-nextarc=G.vertex[i].firstarc;G.vertex[i].firstarc=s;}}voidVisit(GraphG,intu){coutG.vertex[u].data;}intFirstAdjVex(GraphG,intv){if(G.vertex[v].firstarc)returnG.vertex[v].firstarc-adjvex;elsereturn-1;}intNextAdjVex(GraphG,intv,intw){ArcNode*p=G.vertex[v].firstarc;while(p-adjvex!=w)p=p-nextarc;if(p-nextarc)returnp-nextarc-adjvex;elsereturn-1;}voidDFSGrahp(GraphG,intv){visited[v]=true;Visit(G,v);//访问顶点V，对从未访问过的邻接点w递归调用DFS第4页共4页for(intw=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFSGrahp(G,w);}voidDFSTraverse(GraphG){//对图G做深度优先搜索for(intv=0;vG.vexnum;++v)visited[v]=false;//初始化访问标志数组visitedfor(v=0;vG.vexnum;++v)if(!visited[v])DFSGrahp(G,v);//对尚未访问的顶点v调用DFS}voidBFSGrahp(GraphG){//图的广度优先搜索SeqQueueQ;Q=InitQueue();intu;for(intv=0;vG.vexnum;++v)if(!visited[G,v]){EnQueue(Q,v);//v入队列while(!((Q.front==Q.rear)?1:0)){DeQueue(Q,u);//对首元素出队，赋给uvisited[u]=true;Visit(G,u);for(intw=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))//u的未访问过的邻接点w入队列if(!visited[w])EnQueue(Q,w);}}}intmain(){Graphp;intn,e;cout输入图的顶点及边数：endl;cinne;cout创建图：endl;CreateDG(p,n,e);cout图的优先深度结果为：endl;DFSTraverse(p);cout图的广度优先结果为：endl;BFSGrahp(p);printf(结果如上所示!\n);return0;}