图遍历的演示课程设计报告
13页1、合肥学院计算机科学与技术系课程设计报告20 1120 12 学年第 二 学期课程 数据结构与算法课程设计名称 图遍历的演示学生姓名 汪青松学号 1004031010专业班级 网络工程 1 班指导教师 吕刚、陈圣兵2011 年 6 月图遍历的演示一、问题分析和任务定义很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名,如合肥。然后任选国内的城市,起点未合肥,忽略城市间的里程。设图的结点 20-30 个,每个结点用一个编号表示(如果一个图有 n 个结点,则它们的编号分别为 1,2,n)。通过输入图的全部边(存于数据文件中,从文件读写)输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制。注意,生成树的边是有向边,端点顺序不能颠倒。二、数据结构的选择和概要设计城市与城市之间的关系使没有方向的,无向图采用邻近多重表来实现,主要要表示无向图中的各个结点和边,在多重表中边是采用两个结点来表示的。在邻接表中 Edgenode 表示邻接表中的结点类型,其中含有访问标记 mark,一条边所依附的两个结点的序号 ivex
2、和 jvex,以及分别指向依附于 ivex 和jvex 的顶点边的链域 ilink 和 jlink。其中,邻接表中的表头结点用 Vexnode 表示,包含了顶点信息 data 和指向第一个边结点的 firstedge。用 AMLGraph 表示整个无向图,包含了图的顶点 vexnum 和边数 edgenum。结点坐标信息:struct loc /结点坐标信息int v; /结点序号int x; /x 坐标int y; /y 坐标;边结点数据结构:struct Edgenode /边结点 int mark;/标志域,指示该边是否被访问过(0:没有 1:有) int ivex,jvex;/该边关联的两个顶点的位置 Edgenode *ilink,*jlink;/分别指向关联这两个顶点的下一条边 ; 顶点结点:struct Vexnode /顶点结点 int data; /顶点名称,用数字表示城市 Edgenode *firstedge;/指向第一条关联该结点的边 ; AMLGraph 类:AMLGraph- *adjmulist:Vexnode- vexnum:int- edgenum:i
3、nt- maxnum:int+ AMLGraph(num1:int,num2:int)+ AMLGraph()+ Locate_Vex(v:int):int+ AML_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图-1 AMLGraph 类 UML 图三、详细设计和编码程序主体部分主要包括两大部分,一是遍历算法部分;另一部分是对演示图的处理。遍历算法部分主要包括了,邻接多重表构造的无向图的初始化、深度遍历和广度遍历;对演示图的处理包括了,结点坐标信息的初始化和绘图,运用了 graphics.h 库中的绘图函数。1、深度遍历函数名称: void DFS(int v) 函数功能:实现一张无向图从一个指定结点的深度搜索遍历,并输出结点序号函数参数: int v 开始的结点具体代码:void DFS(int v) /深度优先搜
4、索遍历(递归)Edgenode *p;visitedv=1; /标志 v 已被访问coutivex=i)if(visitedp-jvex=0) /邻近点未被访问过 dline(lv.x,lv.y,lp-jvex.x,lp-jvex.y);DFS(p-jvex); /递归调用p=p-ilink;elseif(visitedp-ivex=0)dline(lv.x,lv.y,lp-ivex.x,lp-ivex.y);DFS(p-ivex);/递归调用p=p-jlink; 2、广度遍历函数名称:void BFS(int v) 函数功能:实现一张无向图从一个指定结点的广度度搜索遍历,并输出结点序号;函数参数: int v 开始的结点,返回参数为 void具体代码:void BFS(int v)/广度优先搜索遍历int i,vi;int QueueMAX_VERTEX_NUM,front=0,rear=0; /建立队列数组Edgenode *p;for(i=0;iivex=vi)if(visitedp-jvex=0)/边节点内元素未被访问则访问节点内元素,并对其标记已访问visitedp-jvex
《图遍历的演示课程设计报告》由会员lizhe****0001分享,可在线阅读,更多相关《图遍历的演示课程设计报告》请在金锄头文库上搜索。
亚龙YL-235A光机电一体化实训与考核设备的使用
2016年第三讲比较文学研究对象、种类和范畴
《导游学》第九章导游人员的讲解技能
《施工图识读与会审》3.0.1.1钢结构工程施工图识读与会审
北京嘉利国际商住项目公关活动策划方案
平面解析几何椭圆
植物学第三章第三节叶
财政学第六章财政投资支出和社会保障支出
计算机控制系统(英文版)Chapter1ComputerControlTheoryandDesign
现代物流学第九章电子商务物流
学校管理学第十五章教学媒体的管理
北大《空间探测信息处理技术(IDL)》第7章图像处理(中)
化工基础第二章传热过程
初中英语:上好一堂课的22个关键要素
《田径运动》技术课-跳高2背越式跳高孤线助跑起跳技术
《建筑室内设计》第七章办公空间设计
《城市规划原理》第十章城市历史文化遗传保护与城市更新
《国际金融》Leture4国际金融体系与汇率制度的选择
《中医内科学》第五章肾系病证黄疸
石家庄苹果城商务楼营销策划方案
2022-12-14 10页
2024-01-03 11页
2024-03-01 110页
2023-11-20 25页
2023-10-01 18页
2023-03-26 16页
2023-12-06 4页
2023-07-16 22页
2023-03-23 34页
2023-05-27 76页