图的遍历和生成树求解说明书.doc

*实践教学* 兰州理工大学计算机与通信学院2012年春季学期 算法与数据结构 课程设计题 目：_专业班级：_姓 名：_学 号： 指导教师： 李 睿 成 绩：_目 录摘 要21采用类C语言定义相关数据类型22各模块流程图及伪码算法33函数的调用关系图104调试分析115测试结果126.源程序（见附录）18设计总结19参考文献20致 谢20附件 任务一源程序代码21 摘 要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。关键字：图；深度优先遍历；广度优先遍历；生成树1采用类C语言定义相关数据类型图存储结构的定义：1）顺序存储（邻接矩阵）#define MAX_VERTEX_NUM 30 /最大顶点个数Typedef enumDG,DN,UDG,UDN GraphKind; /图的种类：有向图、有向网、无向图、无向网ArcTypeAdjMtrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /ArcType是顶点关系类型，对无权图，用0和1表示是否相邻，对于网，则为权值类型typedef struct VertexType vexMAX_VERTEX_NUM; /顶点数组 AdjMtrix arc; /邻接矩阵 int vexnum,arcnum; /图中的顶点数和边数 GraphKind kind; /图的种类 GraphMtrix; （2） 邻接表的存储 #define MAX_VERTEX_NUM 30 /最大顶点个数 typedef struct EdgeNode /表结点 int adjvex; /边或弧依赖的顶点序号 InfType *info; /弧或边的相关信息，在网中则为权值 struct EdgeNode *next; EdgeNode; typedef struct VexNode /顶点元素 VertexType vextex; EdgeNode *link; VexNode,AdjListMAX_VERTEX_NUM; typedef struct /邻接表 AdjList vertices; int vexnum,arcnum; /图中的顶点数和边数 GraphKind kind; /图的种类 AdjListGrap2各模块流程图及伪码算法(1) 遍历算法 a.深度优先遍历void DFS(AdjListGraph G,int v)/图G采用邻接表存储结构，v是遍历起始 点在邻接表中的下标值，其下标从0开始visitedv=1; /置已访问标志visite(G.verticesv.vextex); /访问顶点 for (p = G.verticesv.link; p; p = p-next) if (!visitedp-adjvex)DFS(G,p-adjvex); /当前顶点未访问，继续深度优先遍历 / DFSb.广度优先遍历void BFS(AdjListGrap G,intv) /图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标，邻接表中下标从0开始，以队列作为基本辅助数据结构InitQueue(Q); /初始化队列Q visitedv=1; /置已访问标志visite(G.verticesv. vextex); /访问顶点EnQueue(Q,v); /被访问顶点入队 while (!QueueEmpty(Q) DeQueue(Q,v); /出队列 for (p = G.verticesv.link; p; p = p-next) /找所有和v相邻接的顶点 if (!visitedp-adjvex)visitedp-adjvex=1; visite(G.vertices p-adjvex.vextex); EnQueue(Q,p-adjvex); /if /while / BFS(2)流程图a.深度优先遍历dfstraInt i,j;i=0i!=gra.vexnumvisitedi=0+iYj=0j!=gra.vexnumNMultiplex+jreturn0NYb.广度优先遍历BfstraInt i,j;i=0i!=gra.vexnumvisitedi=0+iYj=0j!=gra.vexnumNMultiplex+jreturn0NYc.Prim算法Int lowcostmax ,prevexmaxi=2i=nlowcosti=g1ii +Ylowcost1=0ivexsi)；/*访问顶点vi*/ visitedi=TRUE； for(j=0；jn；j+) /*依次搜索vi的邻接点*/ if(G-edgesij=1&!visitedj) DFSM(G，j)/*(vi，vj)E，且vj未访问过，故vj为新出发点 DFSM*/说明：对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。 当访问某顶点vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。 所以，DFSTraverse的时间复杂度为O(n2) （调用DFSM）或0(n+e)b.深度优先遍历：void BFS(AdjListGrap G,intv) /图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标，邻接表中下标从0开始，以队列作为基本辅助数据结构InitQueue(Q); /初始化队列Q visitedv=1; /置已访问标志visite(G.verticesv. vextex); /访问顶点EnQueue(Q,v); /被访问顶点入队 while (!QueueEmpty(Q) DeQueue(Q,v); /出队列 for (p = G.verticesv.link; p; p = p-next) /找所有和v相邻接的顶点 if (!visitedp-adjvex) visitedp-adjvex=1; visite(G.vertices p-adjvex.vextex); EnQueue(Q,p-adjvex); /if /while / BFSPrim算法：voidPrimAlgorithm(GraphMtrix G,VertexType u)k = VerIndex(G,u); /k为顶点u在图G中的序号for(i=0; i G.vernum; i+) /辅助数组初始化 if(i!=k) closedgei.lowcost = G.arc ki; /当前顶点不在生成树上，应存储该边上的权closedgei. adjvex = k; /依附的在U中的顶点序号初始为k /ifclosedgek.lowcost = 0; /将顶点u并入最小生成树集合，即U=uor(i = 0; i 0,vV-Uprintf(closedgek. adjvex, G. vexk); closedgek.lowcost = 0; /将k对应的顶点并入最小生成树集合，for(j = 0; j G.vernum; j+)if(G.arckj closedgej.lowcost)closedgej.lowcost = G.arcskj;closedgej. adjvex = k; /if /for / PrimAlgorithm 图的存储函数图的创建函数3函数的调用关系图队列初始化函数显示图邻接表函数入队函数出对函数显示图邻接矩阵函数深度优先遍历函数 主函数广度优先遍历函数最小生成树PRIM算法最小生成树KRUSCAL图的连通分量函数4调试分析a.调试中遇到的问题及对问题的解决方法在调试过程中遇到了种种错误，一些错误归属于同一类，总结起来，有以下方面（附带有解决方法）：（1） 头文件加载不正确，缺少了，。加载了相应的头文件后相应错误和警告不再提示。（2） 函数返回值有具体类型是，但是标注为: void .在程序审查后改为了正确的返回类型。（3） 数次插入结点时，插入位置计算有误，打印结果与事实不符，进一步计算后调试正确。（4） 用switch() case ,做选择菜单，没有定义default ,当命令提示符显示菜单后，对于选项之外的选择，程序无法处理。补充后程序完善。b.算法的时间复杂度和空间复杂度（1）图的邻接矩阵存储： 空间复杂度为O(n2) 时间复杂度都为O(n)。（2）图的邻接表表示： 对于有n个顶点，e条边的图，该算法的时间性能为O(n+e)（3）深度优先遍历： 假设n为图中的顶点数，e为边数，则DFS算法的时间复杂性是O(n+e)（4）广度优先遍历： 遍历图的过程实质是对每个顶点查找其邻接点的过程，因此广度优先遍历算法的时间复杂度和深度优先遍历算法的时间复杂度相同，也为O(n+e)，两者的不同之处仅仅在于对顶点的访问顺序不同。（5）分析prim算法： 设连通网中有n个顶点，则第一个进行初始化的循环执行n-1次，第二个循环也执行n-1次，它内嵌两个循环，其一是MinEdge函数在长度为n的数组中查找最小值，需要执行n-1次，其二是修改辅助数组closedge，需要执行n-1次，所以prim算法的时间复杂度为O(n2)，与网中的边数无关5测试结果图3.1创建无向图G图3.2程序主菜单图3.3选择菜单图3.1选择菜单及结束6.源程序（见附录）设计总结从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。通过该题目的设计过程, 自己的编程语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高，加深了对图数据结构及队列的逻辑结构,存储结构及图的深度优先和广度优先遍历过程的理解,对图数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础知识。2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。3.这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很大，学到很多。参考文献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 Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月致 谢本程序得以顺利完成，我首先要感谢张永老师，从课设选题，程序编写修改及最终说明书的出稿，其整个过程都得到了他极大的帮助，她总是在我困惑的时候，给予我指点迷津，诲人不倦。他对我的悉心指导与深深的教诲、启迪，令我收益匪浅。在此，表示深深的敬意和诚挚的谢意。另外要感谢的是我的同学给予我的帮助，论文的完成也离不开平时与他们交流，在这里一并致谢。附件 任务一源程序代码#include#include#include#include using namespace std; #define int_max1 10000#define inf 9999 #define MAX 20/邻接矩阵定义typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; 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(MGraph_L &G) char v1,v2; int i,j,w,k; cout*endl; cout 图的遍历和生成树求解实现 endl; cout*endlendlendl; cout *创建无向图*endlendlendl; coutG.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入顶点iG.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max1;/ /G.arcsij.adj=INT_MAX; G.arcsij.info=NULL; for(k=0;k!=G.arcnum;+k) coutv1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; coutendl#图G邻接矩阵创建成功!#endl; return G.vexnum; /.邻接矩阵.void ljjzprint(MGraph_L G) int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) couttG.arcsij.adj; coutendladjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max1&j!=G.vexnum)/ tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max1&j!=G.vexnum)/ arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; cout #图G邻接表创建成功!#endl; return 1;/.邻接表.void adjprint(algraph gra) int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; coutti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc;return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10;int initqueue(linkqueue &q)/初始化队列 q.rear=(queueptr)malloc(sizeof(qnode); q.front=q.rear; if(!q.front) return 0; q.front-next=NULL; return 1;int enqueue(linkqueue &q,int e)/入队 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;int dequeue(linkqueue &q,int &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;int queueempty(linkqueue q)/判断队为空 if(q.front=q.rear) return 1; return 0;/.广度优先遍历.void bfstra(algraph gra) int i,e; linkqueue q; for(i=0;i!=gra.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); /.深度优先遍历.int dfs(algraph gra,int i);/声明DFSint 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;int dfs(algraph gra,int i) visitedi=1; int we1; cout=0;we=nextadjvex(gra,gra.verticesi,we) we1=we; if(visitedwe=0) dfs(gra,we); we=we1; return 12;/.求连通分量.int bfstra_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); coutendl; return 0;typedef struct int adjvex; int lowcost; closedge;/.最小生成树PRIM算法.int prim(int gMAX,int n) int lowcostMAX,prevexMAX; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点 int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf; return f;/.最小生成树kruscal算法.void kruscal_arc(MGraph_L G,algraph gra) edg edgs20; int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k; int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight;x=edgsi.pre;y=edgsi.bak;n=i; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf;cout(x,y)m;coutendl; /.选择菜单.void choice(algraph gra,MGraph_L G,int d) int i,g2020; char s; couts; if(s7) cout输入错误，请重新选择endl; return; switch(s) case 1: cout*邻接矩阵显示如下*endl; ljjzprint(G); break; case 2: cout*邻接表显示如下*endl; adjprint(gra); break; case 3: cout*广度优先遍历*endl; bfstra(gra); coutendl; break; case 4: for(i=0;i!=gra.vexnum;+i) visitedi=0; cout*深度优先遍历*endl; dfstra(gra); coutendl; break; case 5: for(i=0;i!=G.vexnum;+i) for(int j=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; cout*最小生成树prim算法*endl; prim(g,d); break; case 6: cout*最小生成树kruscal算法*endl; kruscal_arc(G,gra); break; case 7: cout*连通分量*endl; bfstra_fen(gra); break; /.主函数.void main() system(color f1); algraph gra; MGraph_L G; int d; /,g2020; d=creatMGraph_L(G); creatadj(gra,G); coutendlendl !注意：若该图为非强连通图(含有多个连通分量)时!endl !最小生成树不存在,则显示为非法值。!endlendl; cout*菜单*endl; cout 1、显示该图的邻接矩阵 endl; cout 2、显示该图的邻接表 endl; cout 3、深度优先遍历 endl; cout 4、广度优先遍历 endl; cout 5、最小生成树PRIM算法 endl; cout 6、最小生成树KRUSCAL算法 endl; cout 7、该图的连通分量 endlendl;cout*endlendl; char y=n; while(y=y) choice(gra,G,d); coutendly; if(y=n) break; 28