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

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和指向第一个边结点的firstedge。用amlgraph表示整个无向图，包含了

3、图的顶点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;/指向第一条关联该结点的边 ; a

4、mlgraph类：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():vo

5、id图-1 amlgraph类uml图三、详细设计和编码程序主体部分主要包括两大部分，一是遍历算法部分；另一部分是对演示图的处理。遍历算法部分主要包括了，邻接多重表构造的无向图的初始化、深度遍历和广度遍历；对演示图的处理包括了，结点坐标信息的初始化和绘图，运用了graphics.h库中的绘图函数。1、深度遍历函数名称： void dfs(int v) 函数功能：实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号函数参数： int v 开始的结点具体代码： void dfs(int v)/深度优先搜索遍历(递归)edgenode *p;visitedv=1;/标志v已被访问coutviv

6、ex=i)if(visitedp-jvex=0) /邻近点未被访问过 dline(lv.x,lv.y,lp-jvex.x,lp-jvex.y); dfs(p-jvex); /递归调用p=p-ilink; else if(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

7、 v)/广度优先搜索遍历int i,vi;int queuemax_vertex_num,front=0,rear=0; /建立队列数组edgenode *p;for(i=0;ivexnum;i+)/全部节点标记为未访问visitedi=0;visitedv=1; /开始结点标记为已访问coutv; /输出当前访问结点位置coutivex=vi)if(visitedp-jvex=0)/边节点内元素未被访问则访问节点内元素，并对其标记已访问visitedp-jvex=1;coutjvexjvex.x,lp-jvex.y); /绘制路径rear=(rear+1)%max_vertex_num;/队

8、列的尾指针计数器加一，即后移一位queuerear=p-jvex;p=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() ifst

9、ream icin;icin.open(d:wenjian2.txt); int i,j,k;int edge302;/二维数组来存储边的关系,30条边和ivex，jvex边集的两结点 for(i=0;iedgenum;i+)for(j=0;jedgeij;for(i=0;ivexnum;i+) /初始化顶点 adjmulisti.data=i+1; adjmulisti.firstedge=null; for(k=0;kivex=edgek0;e-jvex=edgek1;/读入2个顶点的值e-ilink=adjmuliste-ivex.firstedge;/将头结点的firstedge指针赋

10、给新结点的ilinkadjmuliste-ivex.firstedge=e;/将头结点的指针指向新结点e-jlink=adjmuliste-jvex.firstedge;/将新结点的jlink指针指向其jvex结点所依附的结点adjmuliste-jvex.firstedge=e; init_location(); /初始化所有结点的坐标信息 4、初始化顶点坐标函数名称：void init_location()函数功能：此函数为初始化顶点坐标，主要用来读取存储在文件中的各个顶点坐标信息函数参数：形参为空，返回值为空具体代码： void init_location() /初始化结点的坐标信息if

11、stream icin;l=new loc20;icin.open(d:wenjian1.txt);for(int i=1;ili.vli.xli.y;4、 上机调试过程 图-2 具体的图关系图 图-3 存储顶点坐标信息文件5、 测试结果及其分析图-4 深度搜索遍历结果图-5深度搜索遍历演示图-6 广度搜索遍历演示图-7 广度度搜索遍历演示六、用户使用说明本程序采用c+语言在windows 7+vc6.0环境下编写，主要功能是演示图的两种遍历过程；程序所默认演示无向图包括26个结点和30条边，其中26个结点数字分别代表26个省会城市，30条边表示他们之间的关系，具体关系如演示图所示；进入软件界

12、面后，首先需要输入开始进行遍历的城市位置（即对应的结点数字），然后再进行选择进行图遍历的方式，本程序提供2种图遍历方式，深度优先遍历和广度优先遍历，选择遍历方式后，遍历结果将之间显示在屏幕上，左边数字为访问的结点，右边边集是访问时所经过的边。在运行程序之前，请确保系统装有easyx的graphicsk库。七、参考文献1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。2 编程中国：/thread-329777-1-1.html3 easyx：8、 附录详细代码：graph.h#include #in

13、clude #include #include /#include image.husing namespace std; #define max_vertex_num 30/顶点最大个数bool visited100; /顶点是否被访问标志 struct loc /结点坐标信息int v; /结点序号int x; /x坐标int y; /y坐标;/邻接多重表的存储 struct edgenode/边结点 int mark;/标志域，指示该边是否被访问过(0:没有1:有) int ivex,jvex;/该边关联的两个顶点的位置 edgenode *ilink,*jlink;/分别指向关联这两个

14、顶点的下一条边 ; struct vexnode/顶点结点 int data; /顶点名称,用数字表示城市 edgenode *firstedge;/指向第一条关联该结点的边 ; class amlgraph private: loc *l; /坐标信息指针 vexnode *adjmulist; /顶点数组指针 int vexnum; /定点数目 int edgenum; /边数目 int maxnum; /顶点数最大值 public: /构造函数 amlgraph(int num1=26,int num2=30) adjmulist=new vexnodenum1; vexnum=num1

15、;edgenum=num2; maxnum=max_vertex_num; /析构函数 amlgraph() deleteadjmulist; /定位顶点在顶点数组中的位置 int locate_vex(int v) for(int i=0;ivexnum;i+) if(adjmulisti.data)=v) return i; return -1; /构造无向图 void aml_init() ifstream icin;icin.open(d:wenjian2.txt); int i,j,k;int edge302;/二维数组来存储边的关系,30条边和ivex，jvex边集的两结点 for

16、(i=0;iedgenum;i+)for(j=0;jedgeij; for(i=0;ivexnum;i+) /初始化顶点 adjmulisti.data=i+1; adjmulisti.firstedge=null; for(k=0;kivex=edgek0;e-jvex=edgek1;/读入2个顶点的值e-ilink=adjmuliste-ivex.firstedge;/将头结点的firstedge指针赋给新结点的ilinkadjmuliste-ivex.firstedge=e;/将头结点的指针指向新结点e-jlink=adjmuliste-jvex.firstedge;/将新结点的jlin

17、k指针指向其jvex结点所依附的结点adjmuliste-jvex.firstedge=e; init_location(); /初始化所有结点的坐标信息 /深度优先遍历 void dfs_traverse() for(int i=0;ivexnum;i+) visitedi=false;/初始化所有顶点未被访问过 for(i=0;ivexnum;i+) if(!visitedi)/如果未被访问过，进行访问dfs遍历 dfs(i); coutendl; void dfs(int v)/深度优先搜索遍历(递归)edgenode *p;visitedv=1;/标志v已被访问coutvivex=i)

18、if(visitedp-jvex=0) /邻近点未被访问过 dline(lv.x,lv.y,lp-jvex.x,lp-jvex.y); dfs(p-jvex); /递归调用p=p-ilink; else if(visitedp-ivex=0) dline(lv.x,lv.y,lp-ivex.x,lp-ivex.y); dfs(p-ivex);/递归调用 p=p-jlink; /广度优先遍历 void bfs_traverse() for(int i=0;ivexnum;i+) visitedi=false; for(i=0;ivexnum;i+) if(!visitedi) bfs(i); c

19、outendl; void bfs(int v)/广度优先搜索遍历int i,vi;int queuemax_vertex_num,front=0,rear=0; /建立队列数组edgenode *p;for(i=0;ivexnum;i+)/全部节点标记为未访问visitedi=0;visitedv=1; /开始结点标记为已访问coutv; /输出当前访问结点位置coutivex=vi)if(visitedp-jvex=0)visitedp-jvex=1;coutjvexjvex.x,lp-jvex.y); rear=(rear+1)%max_vertex_num; queuerear=p-j

20、vex;p=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; void dline(int x1,int y1,int x2,int y2) /画线setlinestyle(ps_dash, null, 3); /设置线形为宽度 3 像素的虚线line(x1,y1,x2,y2);void init_location() /初始化结点的坐标信息ifstream icin;l=new loc20;icin.open(d:wenjian1.txt);for(int i=1;ili.vli.xli.y;void image()/绘制矢量无向图hwnd hwnd = gethwnd();/ 使用 api 函数修改窗口名称setw