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

《图的遍历和生成树求解说明书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*******************实践教学*******************兰州理工大学计算机与通信学院2012年春季学期算法与数据结构课程设计题目：______________专业班级：_______________姓名：_______________学号：指导教师：李睿成绩：_______________28目录摘要21．采用类C语言定义相关数据类型22．各模块流程图及伪码算法33．函数的调用关系图104．调试分析115．测试结果126.源程序（见附录）18设计总结19参考文献20致谢20附件Ⅰ任务一源程序代码2

2、128摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。关键字：图；深度优先遍历；广度优先遍历；生成树1．采用类C语言定义相关数据类型图存储结构的定义：1）顺序存储（邻接矩阵）#defineMAX_VERTE

3、X_NUM30//最大顶点个数Typedefenum{DG,DN,UDG,UDN}GraphKind;//图的种类：有向图、有向网、无向图、无向网ArcTypeAdjMtrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//ArcType是顶点关系类型，对无权图，用0和1表示是否相邻，对于网，则为权值类型typedefstruct{VertexTypevex[MAX_VERTEX_NUM];//顶点数组AdjMtrixarc;//邻接矩阵intvexnum,arcnum;//图中的顶点数和边数Graph

4、Kindkind;//图的种类}GraphMtrix;（2）邻接表的存储#defineMAX_VERTEX_NUM30//最大顶点个数typedefstructEdgeNode{//表结点intadjvex;//边或弧依赖的顶点序号InfType*info;//弧或边的相关信息，在网中则为权值structEdgeNode*next;}EdgeNode;typedefstructVexNode{//顶点元素VertexTypevextex;EdgeNode*link;}VexNode,AdjList[MAX_VERTEX_NU

5、M];typedefstruct{//邻接表AdjListvertices;intvexnum,arcnum;//图中的顶点数和边数28GraphKindkind;//图的种类}AdjListGrap2．各模块流程图及伪码算法(1)遍历算法a.深度优先遍历voidDFS(AdjListGraphG,intv)//图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标值，其下标从0开始{visited[v]=1;//置已访问标志visite(G.vertices[v].vextex);//访问顶点for(p=G.vertice

6、s[v].link;p;p=p->next)if(!visited[p->adjvex])DFS(G,p->adjvex);//当前顶点未访问，继续深度优先遍历}//DFSb.广度优先遍历voidBFS(AdjListGrapG,intv)//图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标，邻接表中下标从0开始，以队列作为基本辅助数据结构{InitQueue(Q);//初始化队列Qvisited[v]=1;//置已访问标志visite(G.vertices[v].vextex);//访问顶点EnQueue(Q,v);

7、//被访问顶点入队while(!QueueEmpty(Q)){DeQueue(Q,v);//出队列for(p=G.vertices[v].link;p;p=p->next)//找所有和v相邻接的顶点if(!visited[p->adjvex]){visited[p->adjvex]=1;visite(G.vertices[p->adjvex].vextex);EnQueue(Q,p->adjvex);}//if}//while}//BFS28(2)流程图a.深度优先遍历dfstra28Inti,j;i=0i!=gra.vex

8、numvisited[i]=0++iYj=0j!=gra.vexnumNMultiplex++jreturn0NYb.广度优先遍历Bfstra28Inti,j;i=0i!=gra.vexnumvisited[i]=0++iYj=0j!=gra.vexnumNMultiplex++jretu