《图遍历的演示课程设计报告》由会员分享，可在线阅读，更多相关《图遍历的演示课程设计报告（13页珍藏版）》请在金锄头文库上搜索。
1、合肥学院计算机科学与技术系课程设计报告20 1120 12 学年第 二 学期课程 数据结构与算法课程设计名称 图遍历的演示学生姓名 汪青松学号 1004031010专业班级 网络工程 1 班指导教师 吕刚、陈圣兵2011 年 6 月图遍历的演示一、问题分析和任务定义很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名，如合肥。然后任选国内的城市，起点未合肥，忽略城市间的里程。设图的结点 20-30 个，每个结点用一个编号表示(如果一个图有 n 个结点，则它们的编号分别为 1，2，n)。通过输入图的全部边(存于数据文件中，
2、从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。二、数据结构的选择和概要设计城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。在邻接表中 Edgenode 表示邻接表中的结点类型，其中含有访问标记 mark，一条边所依附的两个结点的序号 ivex 和 jvex，以及分别指向依附于 ivex 和jvex 的顶点边的链域 ilink 和 jlink。其中，邻接表中的表头结点用 Vexnode 表示，包含了顶点信息 data 和指向第一个边结点的 f
3、irstedge。用 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; /顶点名称,用数字表示城
4、市 Edgenode *firstedge;/指向第一条关联该结点的边 ; AMLGraph 类：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):v
5、oid+ Mark_Unvisited():void+ Display():void图-1 AMLGraph 类 UML 图三、详细设计和编码程序主体部分主要包括两大部分，一是遍历算法部分；另一部分是对演示图的处理。遍历算法部分主要包括了，邻接多重表构造的无向图的初始化、深度遍历和广度遍历；对演示图的处理包括了，结点坐标信息的初始化和绘图，运用了 graphics.h 库中的绘图函数。1、深度遍历函数名称： void DFS(int v) 函数功能：实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号函数参数： int v 开始的结点具体代码：void DFS(int v) /深度优先搜
6、索遍历(递归)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) 函数功能：实现一张无向图从一个指定结点的广度度搜索遍历，并输出结点序号；函数
7、参数： 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=1;coutjvexjvex.x,lp-jvex.y); /绘制路径rear=(rear+1)%MAX_VERTEX_NUM;/队列的尾指针计数器加一，即后移一位Queuerear=p-jvex;p
8、=p-ilink;/边节点内元素已被访问，指向下一邻接点elseif(visitedp-ivex=0)visitedp-ivex=1;coutivexivex.x,lp-ivex.y); /绘制路径rear=(rear+1)%MAX_VERTEX_NUM;Queuerear=p-ivex;p=p-jlink;3、图的创建和初始化函数名称：void AML_Init()函数功能：创建一张固定结点和边数的无向图，边与结点的关系是从文件中读取函数参数：形参为空，返回也为 void具体代码：void AML_Init() ifstream icin;icin.open(d:wenjian2.txt);
9、 int i,j,k;int edge302;/二维数组来存储边的关系,30 条边和 ivex，jvex 边集 的两结点for(i=0;iedgeij;for(i=0;iivex=edgek0;e-jvex=edgek1;/读入 2 个顶点的值e-ilink=adjmuliste-ivex.firstedge;/将头结点的 firstedge指针赋给新结点的 ilinkadjmuliste-ivex.firstedge=e;/将头结点的指针指向新结点e-jlink=adjmuliste-jvex.firstedge;/将新结点的 jlink 指针指向其 jvex 结点所依附的结点adjmuli
10、ste-jvex.firstedge=e; init_location(); /初始化所有结点的坐标信息 4、初始化顶点坐标函数名称：void init_location()函数功能：此函数为初始化顶点坐标，主要用来读取存储在文件中的各个顶点坐标信息函数参数：形参为空，返回值为空具体代码：void init_location() /初始化结点的坐标信息ifstream icin;l=new loc20;icin.open(d:wenjian1.txt);for(int i=1;ili.vli.xli.y;4、上机调试过程图-2 具体的图关系图 图-3 存储顶点坐标信息文件5、测试结果及其分析图
11、-4 深度搜索遍历结果图-5 深度搜索遍历演示图-6 广度搜索遍历演示图-7 广度度搜索遍历演示六、用户使用说明本程序采用 C+语言在 Windows 7+VC6.0 环境下编写，主要功能是演示图的两种遍历过程；程序所默认演示无向图包括 26 个结点和 30 条边，其中 26 个结点数字分别代表 26 个省会城市，30 条边表示他们之间的关系，具体关系如演示图所示；进入软件界面后，首先需要输入开始进行遍历的城市位置（即对应的结点数字） ，然后再进行选择进行图遍历的方式，本程序提供 2 种图遍历方式，深度优先遍历和广度优先遍历，选择遍历方式后，遍历结果将之间显示在屏幕上，左边数字为访问的结点，右
12、边边集是访问时所经过的边。在运行程序之前，请确保系统装有 Easyx 的 graphicsk 库。七、参考文献1 王昆仑，李红 . 数据结构与算法. 北京：中国铁道出版社，2006 年 5 月。2 编程中国：http:/ Easyx：http:/8、附录详细代码：graph.h#include #include #include #include /#include image.husing namespace std; #define MAX_VERTEX_NUM 30/顶点最大个数bool visited100; /顶点是否被访问标志 struct loc /结点坐标信息int v; /结
13、点序号int x; /x 坐标int y; /y 坐标;/邻接多重表的存储 struct Edgenode /边结点 int mark;/标志域，指示该边是否被访问过(0:没有 1:有) int ivex,jvex;/该边关联的两个顶点的位置 Edgenode *ilink,*jlink;/分别指向关联这两个顶点的下一条边 ; struct Vexnode /顶点结点 int data; /顶点名称,用数字表示城市Edgenode *firstedge;/指向第一条关联该结点的边 ; class AMLGraph private: loc *l; /坐标信息指针Vexnode *adjmuli
14、st; /顶点数组指针 int vexnum; /定点数目 int edgenum; /边数目 int maxnum; /顶点数最大值 public: /构造函数AMLGraph(int num1=26,int num2=30) adjmulist=new Vexnodenum1; vexnum=num1;edgenum=num2;maxnum=MAX_VERTEX_NUM; /析构函数AMLGraph() deleteadjmulist; /定位顶点在顶点数组中的位置 int Locate_Vex(int v) for(int i=0;iedgeij;for(i=0;iivex=edgek0
15、;e-jvex=edgek1;/读入 2 个顶点的值e-ilink=adjmuliste-ivex.firstedge;/将头结点的 firstedge 指针赋给新结点的 ilinkadjmuliste-ivex.firstedge=e;/将头结点的指针指向新结点e-jlink=adjmuliste-jvex.firstedge;/将新结点的 jlink 指针指向其jvex 结点所依附的结点adjmuliste-jvex.firstedge=e; init_location(); /初始化所有结点的坐标信息 /深度优先遍历 void DFS_Traverse() for(int i=0;iivex=i)if(visitedp-jvex=0) /邻近点未被访问过
