数据结构课程设计文档-图的遍历

2012级计算机科学与技术专业《数据结构》课程设计文档设计题目图的遍历班级12网路工程组长学号3121101124姓名庄俊坤学号3121101135姓名林捷学号3121101136姓名周柏煌学号3121101160姓名赵云鹏学号3111101119姓名谢国印完成日期2014.1前言图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。一、设计题目图遍历的演示二、实验目的：本课程设计是《数据结构》课程的组成之一，也是它的继续和延伸。采用集中学习方法，分组完成一个小型应用系统。开设本课程的目的是使学生通过参加小型软件的开发过程，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；同时培养学生的创新能力和创新意识，锻炼他们的团队协作精神。三、问题描述：由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：①在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。②在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。③在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。④在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。四、功能要求（1）以邻接表作为存储结构；（2）由用户指定遍历的起点；（3）实现深度优先和广度优先遍历；（4）输出深度优先遍历和广度优先遍历的结点访问序列；（5）并给出相应生成树的边集。（6）给出至少3组测试数据，其中图顶点的个数大于10小于30。较高要求：建立深度和广度生成树，按凹入表或树形打印生成树。五、相关原理(1)深度优先搜索法﹕深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Booleanvisited[MAX_VERTEX_NUM];//访问标志数组Status(*VisitFunc)(intv);//VisitFunc是访问函数，对图的每个顶点调用该函数voidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}voidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE;VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。//若w是v的最后一个邻接点，则返回空（0）。if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w调用DFS}(2)广度优先搜索法﹕图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit，并均标记已访问过，然后再按照vi1,vi2,…,vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：Booleanvisited[MAX_VERTEX_NUM];//访问标志数组Status(*VisitFunc)(intv);//VisitFunc是访问函数，对图的每个顶点调用该函数voidBFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;vG.vexnum,++v)visited[v]=FALSE;initQueue(Q);//置空辅助队列Qfor(v=0;vG.vexnum;++v)if(!visited[v]){visited[v]=TRUE;VisitFunc(v);EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w))if(!Visited[w]){//w为u的尚未访问的邻接顶点Visited[w]=TRUE;VisitFunc(w);EnQueue(Q,w);}}}}六、设计方案通过结合教材和网络资料，先分析各个算法的基本实现的方法，然后将基本算法列出，之后根据需要，将各个算法进行整合、使用。图的遍历演示选择存储结构，图的构建深度遍历广度遍历深度遍历边集广度遍历边集七、详细设计1.邻接表的存储表示intvisited[30];#defineMAX_VERTEX_NUM30#defineOK1//typedefintVertexType;typedefintInfoType;//表节点typedefstructArcNode//弧{intadjvex;structArcNode*nextarc;}ArcNode;//头节点typedefstructVNode//表头{intdata;ArcNode*firstarc;//指向第一条依附该定点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];2.图的构建typedefstruct//图{AdjListvertices;intvexnum,arcnum;//顶点数，弧数intkind;//图的种类标志}ALGraph;//邻接表存储表示//图的创建voidCreateDG(ALGraph&G){intk,i,v1;coutendl请输入结点个数:;cinG.vexnum;//节点数cout请输入弧的个数:;cinG.arcnum;//弧数for(i=1;i=G.vexnum;i++)//初使化表头{G.vertices[i].data=i;//初始化顶点值G.vertices[i].firstarc=NULL;//初始化指针}for(k=1;k=G.vexnum;k++)//输入边{intv2;cout请输入与结点k相邻的边数:;cinv2;cout请输入与第k个结点相连的结点编号:;cinv1;ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode));if(!p)exit(-1);p-adjvex=v1;p-nextarc=NULL;G.vertices[k].firstarc=p;for(inti=1;iv2;i++){intm;cout请输入与第k个结点相连的结点编号:;cinm;ArcNode*q;q=(ArcNode*)malloc(sizeof(ArcNode));//动态指针if(!q)exit(-1);q-adjvex=m;//顶点给Pq-nextarc=NULL;p-nextarc=q;p=q;//free(q);}//free(p);}}3.深度优先遍历voidDFS(ALGraphG,intv)//深度搜索{visited[v]=1;coutG.vertices[v].data;ArcNode*x;x=(ArcNode*)malloc(sizeof(ArcNode));if(!x)exit(-1);x=G.vertices[v].firstarc;intw;for(;x;x=x-nextarc){w=x-adjvex;if(visited[w]==0)DFS(G,w);}}voidDFSB(ALGraphG,intv)//深度搜索的边集{visited[v]=1;ArcNode*y;y=(ArcNode*)malloc(sizeof(ArcNode));if(!y)exit(-1);y=G.vertices[v].firstarc;intu=G.vertices[v].data;intw;for(;y;y=y-nextarc){w=y-adjvex;if(visited[w]==0){coutu---wendl;DFSB(G,w);}}}typedefstructQNode{intdata;QNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;4.广度优先遍历voidBFS(ALGraphG,intv)//广度搜索{intu;LinkQueueQ;InitQueue(Q);if(visited[v]==0){visited[v]=1;coutG.vertices[v].data;EnQueue(Q,v);while(QueueEmpty(Q)!=1){DeQueue(Q,u);ArcNode*z;z=(ArcNode*)malloc(sizeof(ArcNode));if(!z)exit(-1);z=G.vertices[u].firstarc;intw;for(;z;z=z-nextarc){w=z-adjvex;if(visited[w]==0){visited[w]=1;coutw;EnQueue(Q,w);}}}}}voidBFSB(ALGraphG,intv)//广度搜索的边集{intu;LinkQueueQ;InitQueue(Q);if(visited[v]==0){visited[v]=1;EnQueue(Q,v);while(QueueEmpty(Q)!=1){DeQueue(Q,u);ArcNode*r;r=(ArcNode*)malloc(sizeof(ArcNode));if(!r)exit(-1);r=G.vertices[u].firstarc;intw;for(;r!=NULL;r=r-nextarc){w=r-adjvex;if(visited[w]==0){visited[w]=1;coutu---wendl;EnQueue(Q,w);}}}}}5.主函数intmain(){inti;ALGraphG;CreateDG(G);intx;cout请输入结点数:;cinx;cout邻接表为：endl;for(intj=1;j=x;j++){coutG.vertices[j].data;ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode));if(!p)exit(-1);p=G.vertices[j].firstarc;while(p){coutp-adjvex;p=p-nextarc;}coutendl;}cout请输入第一个要访问的结点序号：endl;intn;cinn;for(i=0;i30;i++)visited[i]=0;cout广度搜索：endl;BFS(