图的遍历和生成树求解实现

1、目录摘要2序言3正文41.问题描述41.1 .图的遍历和生成树求解实现41.2 基本功能41.3 输入输出42. 逻辑设计42.1 设计思路42.2数据结构设计52. 3软件设计63. 详细设计73.1定义程序中的数据及其数据结构73.2主函数和其他函数的伪码算法83.3主要函数的程序流程图154. 调试分析184.1 实际完成的情况说明184.2 程序的性能分析，时空分析184.3 上机过程中出现的问题及其解决方案184.4 程序中可以改进的地方说明185. 测试结果195.1 主界面195.2 程序运行截图205.3创建一个有权连通图216.使用说明书22设计总结23参考文献24致谢25附

2、录26摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。关键字：图、深度优先遍历、广度优先遍历、生成树。序言计算机科学与技术本科专业算法与数据结构课程设计是在算法与数据结构课程结束之后，要求学生能够设计程序，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于

3、解决实际问题，培养自己的动手能力，独立思考能力，发现问题并解决问题能力而开设的课程。从课程性质上讲，算法与数据结构课程设计是一门技术实践课。其要求是：学会分析研究计算机加工的数据结构的特点，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，在前期学习过程中对复杂程序设计理解掌握基础上做进一步的实践训练，并且能编写出结构清楚，正确易读，符合软件工程规范的程序。很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结

4、构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。由于此题目需要较多的数据输入，同时功能模块也比较的多，故在命令提示符下采用了图形化菜单式的界面，使得选择功能和输入数据都比较容易。正文1. 问题描述1.1 .图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其

5、孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。1.2 基本功能1) 先任意创建一个图；2) 图的dfs,bfs的递归和非递归算法的实现3) 最小生成树（两个算法）的实现，求连通分量的实现4) 要求用邻接矩阵、邻接表等多种结构存储实现1.3 输入输出输入数据类型为整型和字符型，输出为整型和字符2. 逻辑设计2.1 设计思路1) 图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再

6、将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用表示。2) 图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。3) 图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。4) 图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻

7、接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。5) 图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。2.2 数据结构设计adt queue数据对象：d=ai| ai elemset,i=1,2,3，n,n0数据关系：r1=| ai-1,ai d,i=1,2,3,，n基本操作： initqueue(&q) 操作结果：构造一个空队列q。 queueempty(q) 初始条件：q为非空队列。 操作结果：若q为空队列

8、，则返回真，否则为假。 enqueue(&q,e) 初始条件：q为非空队列。 操作结果：插入元素e为q的新的队尾元素。 dequeue(&q,e) 初始条件：q为非空队列。 操作结果：删除q的队头元素，并用e返回其值。adt queueadt graph数据对象v：v是具有相同特性的数据元素的集合，称为顶点集。数据关系r： r=vr vr=|v,wv且p（v，w）,表示从v到w的弧， 谓词p（v,w）定义了弧的意义或信息基本操作p： creatgraph(&g,v,vr); 初始条件：v是图的顶点集，vr是图中弧的集合。 操作结果：按v和vr的定义构造图g。 bfstraverse(g,vis

9、it(); 初始条件：图g存在，visit是定点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点 调用函数visit一次且仅一次。一旦visit（）失 败，则操作失败。 dfstraverse(g,visit(); 初始条件：图g存在，visit是定点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点 调用函数visit一次且仅一次。一旦visit（）失 败，则操作失败。 dfstra_fen(g) 初始条件：图g存在，存在图的深度优先遍历算法。 操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。adt graph;2.3 软件设计函数名返回值类型c

10、reatmgraph_l(g)intcreatadj(gra,g)intljjzprint(g)voidadjprint(gra,g)voidbfstraverse(gra)voiddfstra(gra)intdfstraverse_fen(gra)intminispantree_prim(g,g.vexnum)intminispantree_kruscal(g,gra)void3.详细设计3.1定义程序中的数据及其数据结构1） 邻接矩阵定义:typedef struct arccellvrtype adj;/vrtype是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型in

11、fotype *info;/该弧相关信息的指针arccell,adjmatrixmaxmax;typedef structvertextype vexsmax;/顶点向量adjmatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数mgraph_l;2） 邻接表的定义:typedef struct arcnode/弧结点int adjvex;/该弧指向的顶点的位置struct arcnode *nextarc;/指向下一条弧的指针infotype *info;/该弧相关信息的指针arcnode;typedef struct vnode/邻接链表顶点头接点ve

12、rtextype data;/顶点信息arcnode *firstarc;/指向第一条依附该顶点的弧的指针vnode,adjlist;typedef struct/图的定义adjlist verticesmax;int vexnum,arcnum;/图的当前顶点数和弧数algraph;3） 队列定义:typedef struct qnodeqelemtype data;struct qnode *next;qnode,*queueptr;typedef structqueueptr front;/队头指针queueptr rear;/队尾指针linkqueue;3.2 主函数和其他函数的伪码算

13、法1） 主函数int main()int s;char y=y; cout|菜单|endl; cout|-【0、创建一个无向图-|endl; cout|-【1、显示该图的邻接矩阵-|endl; cout|-【2、显示该图的邻接表-|endl;cout|-【3、广度优先遍历-|endl; cout|-【4、深度优先遍历-|endl; cout|-【5、最小生成树minispantree_prim算法-|endl; cout|-【6、最小生成树minispantree_kruscal算法-|endl; cout|-【7、连通分量-|endl;cout|endl;while(y=y)cout请选择菜

14、单：s;if(s=0)+o;if(o=2)n=0;l=0;o=0;switch(s)case 0:cout创建一个无向图：endl;mgraph_l g;creatmgraph_l(g);algraph gra;creatadj(gra,g); break;case 1:cout邻接矩阵显示如下：endl;ljjzprint(g); break; case 2: cout邻接表显示如下：endl; adjprint(gra,g); break; case 3: cout广度优先遍历：; bfstraverse(gra); coutendl; break; case 4:cout深度优先遍历：;

15、 dfstra(gra); coutendl; break; case 5:if(n=0)cout0)cout若该图为非强连通图(含有多个连通分量)时，最小生成树不存在endl;break;elseint i,gmaxmax;for(i=0;i!=g.vexnum;+i)for(int j=0;j!=g.vexnum;+j)gi+1j+1=g.arcsij.adj;cout普利姆算法:endl;minispantree_prim(g,g.vexnum);break; case 6:if(n=0)cout0)cout该图为非强连通图(含有多个连通分量)，最小生成树不存在endl;break;el

16、secout克鲁斯卡尔算法:endl; minispantree_kruscal(g,gra); break; case 7:cout连通分量:endl;dfstraverse_fen(gra); break;coutendly; if(y=n) break;return 0;2） 邻接矩阵存储int creatmgraph_l(mgraph_l &g)/创建图用邻接矩阵表示char v1,v2;int i,j,w;cout请输入顶点和弧的个数g.vexnumg.arcnum;cout输入各个顶点endl;for(i=0;ig.vexsi;for(i=0;ig.vexnum;+i)for(j=

17、0;jg.vexnum;+j)g.arcsij.adj=int_max;g.=null;for(int k=0;kg.arcnum;+k)cout输入一条边依附的顶点和权v1v2w;/输入一条边依附的两点及权值i=localvex(g,v1);/确定顶点v1和v2在图中的位置j=localvex(g,v2);g.arcsij.adj=w;g.arcsji.adj=w;for(i=0;i!=g.vexnum;+i)for(j=0;j!=g.vexnum;+j)if(g.arcsij.adj!=1&g.arcsij.adj=1)cout这是一个有权图endl;else cou

18、t这是一个无权图endl;cout图g邻接矩阵创建成功！endl;return g.vexnum;3） 邻接矩阵的输出void ljjzprint(mgraph_l g) /邻接矩阵的输出int i,j;if(n=0)for(i=0;i!=g.vexnum;+i)for(j=0;j!=g.vexnum;+j)if(g.arcsij.adj=int_max)cout0 ;else coutg.arcsij.adj ;coutendl;elsefor(i=0;i!=g.vexnum;+i)for(j=0;j!=g.vexnum;+j)if(g.arcsij.adj=int_max)cout ;el

19、se coutg.arcsij.adj ;coutadjvex=j;arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=g.vexnum;gra.arcnum=g.arcnum;cout图g邻接表创建成功！endl;return 1;5） 邻接表输出void adjprint(algraph gra,mgraph_l g) /邻接表输出int i;for(i=0;i!=gra.vexnum;+i)arcnode *p;couti,g.vexsi;p=gra.verticesi.firstarc;whi

20、le(p!=null)coutadjvexnextarc;coutend;coutnext=null;return 1;7） 入队status enqueue(linkqueue &q,qelemtype e)/入队,插入元素e为q的新的队尾元素queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)return 0;/存储分配失败p-data=e;p-next=null;q.rear-next=p;q.rear=p;return 1;8） 出队status dequeue(linkqueue &q,qelemtype &e)/出队，若队列不空，则删

21、除q的队头元素，用e返回，并返回真，否则假queueptr p;if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return 1;9） 判断队为空status queueempty(linkqueue q)/判断队为空if(q.front=q.rear) return 1;return 0;10） 广度优先遍历void bfstraverse(algraph gra)int i,e;linkqueue q;for(i=0;i!=gr

22、a.vexnum;+i)visitedi=0;initqueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;enqueue(q,we);11） 深度优先遍历int dfs(algraph gra,int i)visitedi=1;int we1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(v

23、isitedwe=0)dfs(gra,we);we=we1;return 1;int dfstra(algraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);return 0;12） 连通分量int dfstraverse_fen(algraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);c

24、out0为有权图，此时输出的时候用代替10000；n=0为无权图，此时输出的时候用0代替10000.2）程序中有的功能对某些图是不适用的，比如无权图没有最小生成树，非强连通图没有最小生成树等。所以在程序中又新增了全局变量l,l0时表示为非强连通图，则在求最小生成树时报错。3）当程序先创建一个有权图后，n的值会大于1，第二次创无权图时也会被程序认为有权图，所以在程序中在定义全局变量o（初值为0）,来判断创建了几次图，当第二次创建图，即o=2时，所有全局变量在开始全归零。4.4 程序中可以改进的地方说明当建立一个图时先得求其连通分量，从而确定全局变量l的值，从而才能判断该图是否有最小生成树。5.

25、测试结果5.1 主界面5.2程序运行截图 5.3 创建一个有权连通图6. 使用说明书 1）先选0创建一个图。2）选择y继续操作。3）按照菜单编码选择操作。设计总结在做这个程序的时候你首先必须知道图的一些概念，图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。当我们拿到一个图时，我们对该图的遍历

26、就要有一些方法，所以有了深度优先遍历和广度优先遍历，我们要明白这两种遍历是怎么实现的，然后根据我们人脑中的方法把它写成电脑算法。对一个图我们还定义了连通分量，所以将图存到电脑中时，我们对连通分量得有个算法。求图的最小生成树有两种算法，普利姆是从结点出发寻找权最小的边，知道所有结点都练通了；而克鲁斯卡尔算法则是从边出发，寻找使图连通的权值最小边的方法。算法的实现从人脑到电脑的转变是比较复杂的一件事，要求做到具体到实现该方法的每一个步骤，然后再将每一个步骤通过代码实现。这要求我们要明确各个数据元素和个元素之间的关系，然后才能明确使用算法去调用这些数据。通过本次的课程设计，我对数据结构有了一定的认识

27、，明白了数据结构中数据，数据关系，及对其操作的方法。但同时也发现在自己有很多的不足，在使用语言和如何精炼语言需要进行更多的训练。参考文献1 严蔚敏，吴伟民.数据结构（c语言版）.清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（c语言版）.清华大学出版社.3 data structure with c+. william ford,william topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社. 5数据结构与算法分析（java版） , a practical introduction to data structures and algorithm ana

28、lysis java edition clifford a. shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月致谢在这次课程设计的撰写过程中，我得到了许多人的帮助。首先我要感谢我的老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计商的难题。同时也感谢学院为我提供良好的做毕业设计的环境。最后再一次感谢所有在设计中曾经帮助过我的良师益友

29、和同学附录源代码#include #include using namespace std;#define int_max 10000/最大值static int n=0;/全局变量，判断有权图和无权图static int o=0;/全局变量，清除bugstatic int l=0;/全局变量，清除bug#define inf 9999/最小值的最大值#define max 20/最大顶点个数typedef int vrtype,qelemtype,status;typedef char infotype,vertextype; /|邻接矩阵|/-邻接矩阵定义-typedef struct a

30、rccellvrtype adj;/vrtype是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型infotype *info;/该弧相关信息的指针arccell,adjmatrixmaxmax;typedef structvertextype vexsmax;/顶点向量adjmatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数mgraph_l;/-int localvex(mgraph_l g,char v)/返回v的位置int i=0;while(g.vexsi!=v)+i;return i;int creatmgraph_l(mg

31、raph_l &g)/创建图用邻接矩阵表示char v1,v2;int i,j,w;cout请输入顶点和弧的个数g.vexnumg.arcnum;cout输入各个顶点endl;for(i=0;ig.vexsi;for(i=0;ig.vexnum;+i)for(j=0;jg.vexnum;+j)g.arcsij.adj=int_max;g.=null;for(int k=0;kg.arcnum;+k)cout输入一条边依附的顶点和权v1v2w;/输入一条边依附的两点及权值i=localvex(g,v1);/确定顶点v1和v2在图中的位置j=localvex(g,v2);g.

32、arcsij.adj=w;g.arcsji.adj=w;for(i=0;i!=g.vexnum;+i)for(j=0;j!=g.vexnum;+j)if(g.arcsij.adj!=1&g.arcsij.adj=1)cout这是一个有权图endl;else cout这是一个无权图endl;cout图g邻接矩阵创建成功！endl;return g.vexnum;void ljjzprint(mgraph_l g) /邻接矩阵的输出int i,j;if(n=0)for(i=0;i!=g.vexnum;+i)for(j=0;j!=g.vexnum;+j)if(g.arcsij.adj=int_max

33、)cout0 ;else coutg.arcsij.adj ;coutendl;elsefor(i=0;i!=g.vexnum;+i)for(j=0;j!=g.vexnum;+j)if(g.arcsij.adj=int_max)cout ;else coutg.arcsij.adj ;coutadjvex=j;arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=g.vexnum;gra.arcnum=g.arcnum;cout图g邻接表创建成功！endl;return 1;void adjprint(

34、algraph gra,mgraph_l g) /邻接表输出int i;for(i=0;i!=gra.vexnum;+i)arcnode *p;couti,g.vexsi;p=gra.verticesi.firstarc;while(p!=null)coutadjvexnextarc;coutend;coutnext=null;return 1;status enqueue(linkqueue &q,qelemtype e)/入队,插入元素e为q的新的队尾元素queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)return 0;/存储分配失败p-

35、data=e;p-next=null;q.rear-next=p;q.rear=p;return 1;status dequeue(linkqueue &q,qelemtype &e)/出队，若队列不空，则删除q的队头元素，用e返回，并返回真，否则假queueptr p;if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return 1;status queueempty(linkqueue q)/判断队为空if(q.front=q.rear) return 1;return 0;/-图的遍历-int visitedmax;/访问标记int we;int firstadjvex(algraph gra,vnode v)/返回依附顶点v的第一个点 /即以v为尾的第一个结点if(v.firstarc!=nu