1、 计算机科学与技术系 课程设计报告 20 1120 12 学年第 二 学期 课程 数据结构与算法 课 程 设 计 名 称 图遍历的演示 学生姓名 学号 专业班级 网络工程 1 班 指导教师 2011 年 6 月 图遍历的演示 一、问题分析和任务定义一、问题分析和任务定义 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演 示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名，如合肥。 然后任选国内的城市，起点未合肥，忽略城市间的里程。 设图的结点 20-30 个，每个结点用一个编号表示(如果一个图有 n 个结点， 则它们的编号分别为 1，2，n)。通过输入图的全部边(存
2、于数据文件中，从 文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。 注意，生成树的边是有向边，端点顺序不能颠倒。 二、数据结构的选择和概要设计二、数据结构的选择和概要设计 城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要 要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。 在邻接表中 Edgenode 表示邻接表中的结点类型，其中含有访问标记 mark， 一条边所依附的两个结点的序号ivex和jvex， 以及分别指向依附于ivex和jvex 的顶点边的链域 ilink 和 jlink。 其中，邻接表中的表头结点用 Vexnode 表示，
3、包含了顶点信息 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;/分别指向关联这两个顶点的下一条边
4、; 顶点结点：顶点结点： struct Vexnode /顶点结点 int data; /顶点名称,用数字表示城市 Edgenode *firstedge;/指向第一条关联该结点的边 ; AMLGrapAMLGraph h 类：类： AMLGraph - *adjmulist：Vexnode - vexnum：int - edgenum：int - 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 图 三、详细设计和
