图遍历的演示课程设计报告

《图遍历的演示课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2011～2012学年第二学期课程数据结构与算法课程设计名称图遍历的演示学生姓名汪青松学号1004031010专业班级网络工程1班指导教师吕刚、陈圣兵2011年6月图遍历的演示一、问题分析和任务定义很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名，如合肥。然后任选国内的城市，起点未合肥，忽略城市间的里程。设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为

2、1，2，…，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。二、数据结构的选择和概要设计城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。在邻接表中Edgenode表示邻接表中的结点类型，其中含有访问标记mark，一条边所依附的两个结点的序号ivex和jvex，以及分别指向依附于ivex和jvex的顶点边的链域il

3、ink和jlink。其中，邻接表中的表头结点用Vexnode表示，包含了顶点信息data和指向第一个边结点的firstedge。用AMLGraph表示整个无向图，包含了图的顶点vexnum和边数edgenum。结点坐标信息：structloc//结点坐标信息{intv;//结点序号intx;//x坐标inty;//y坐标};边结点数据结构：structEdgenode//边结点{intmark;//标志域，指示该边是否被访问过(0:没有1:有)intivex,jvex;//该边关联的两个顶点的位置Edge

4、node*ilink,*jlink;//分别指向关联这两个顶点的下一条边};顶点结点：structVexnode//顶点结点{intdata;//顶点名称,用数字表示城市Edgenode*firstedge;//指向第一条关联该结点的边};AMLGraph类：AMLGraph-*adjmulist：Vexnode-vexnum：int-edgenum：int-maxnum：int+AMLGraph(num1:int,num2:int)+~AMLGraph()+Locate_Vex(v:int):int+A

5、ML_Init():void+Judge_Edge(v1:int,v2:int):bool+DFS_Traverse():void+DFS(v:int):void+BFS_Traverse():void+BFS(v:int):void+Mark_Unvisited():void+Display():void图-1AMLGraph类UML图三、详细设计和编码程序主体部分主要包括两大部分，一是遍历算法部分；另一部分是对演示图的处理。遍历算法部分主要包括了，邻接多重表构造的无向图的初始化、深度遍历和广度遍历；对

6、演示图的处理包括了，结点坐标信息的初始化和绘图，运用了graphics.h库中的绘图函数。1、深度遍历函数名称：voidDFS(intv)函数功能：实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号函数参数：intv开始的结点具体代码：voidDFS(intv)//深度优先搜索遍历(递归){Edgenode*p;visited[v]=1;//标志v已被访问cout<

7、e(p!=NULL)//依次搜索v的邻接点{if(p->ivex==i){if(visited[p->jvex]==0)//邻近点未被访问过{dline(l[v].x,l[v].y,l[p->jvex].x,l[p->jvex].y);DFS(p->jvex);//递归调用}p=p->ilink;}else{if(visited[p->ivex]==0){dline(l[v].x,l[v].y,l[p->ivex].x,l[p->ivex].y);DFS(p->ivex);//递归调用}p=p->jlin

8、k;}}}2、广度遍历函数名称：voidBFS(intv)函数功能：实现一张无向图从一个指定结点的广度度搜索遍历，并输出结点序号；函数参数：intv开始的结点，返回参数为void具体代码：voidBFS(intv)//广度优先搜索遍历{inti,vi;intQueue[MAX_VERTEX_NUM],front=0,rear=0;//建立队列数组Edgenode*p;for(i=0;i