《图的遍历和生成树的求解实现》由会员分享，可在线阅读，更多相关《图的遍历和生成树的求解实现（34页珍藏版）》请在金锄头文库上搜索。
1、 计算机与通信学院 2009 年春季学期数据结构课程设计题目：图的遍历和生成树求解实现专业班级：09 级计算机科学与技术 4 班学生姓名：李红军学号：09240407指导老师：张其文成绩： 目 录摘要 .序言 .正 文 .1.问题描述 52.采用类 C 语言定义相关的数据类型 53.函数的调用关系图 84.各模块流程图及伪码算法 95.调试分析13设 计 总 结 17参考文献 .18致谢 .19附录 .20 摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树） 。通过该题目的设计过程，可以加深理解图数据结构及队列
2、的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。关键词：图、深度优先遍历、广度优先遍历、生成树。 序言 我们对教学计划有一个系统的认识，大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。通过该题目的设
3、计过程，可以加深理解数据的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。通过本次课程设计的制作，能让我们对数据结构以及程序设计有更深的体会，流程图的建立能提高我们系统分析问题的能力，从而灵活的驾驭整个程序的运行，通过对图的顶点的存储，让我们加深对邻接表的应用，更重要的是拓扑排序的复习，大一时，我们曾在离散数学中学习了拓扑排序，此次课程设计不进能让我们学习数据结构的知识，同时也能让我们系统复习一下图论的知识。 正 文1. 问题描述为了更好地学习数据结构课程，理解和掌握算法设计所需的技术，为整
4、个专业学习打好基础。运用所学知识，上机解决典型问题，通过分析、设计、编码、调试等各环节的训练，使我深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，掌握线性链表、树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。实现图的遍历、求生成树等的相关操作。通过该题目的设计过程，可以加深理解图、顺序表的逻辑结构、存储结构，掌握与与图相关基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，进一
5、步培养学生的动手能力。2.采用类 c 语言定义相关的数据类型图存储结构的定义：1）顺序存储（邻接矩阵）#define MAX_VERTEX_NUM 30 /最大顶点个数Typedef enumDG,DN,UDG,UDN GraphKind; /图的种类：有向图、有向网、无向图、无向网ArcType AdjMtrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /ArcType 是顶点关系类型，对无权图，用 0 和 1 表示是否相邻，对于网，则为权值类型typedef struct VertexType vexMAX_VERTEX_NUM; /顶点数组AdjMtrix arc; /
6、邻接矩阵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,AdjListM
7、AX_VERTEX_NUM;typedef struct /邻接表AdjList vertices;int vexnum,arcnum; /图中的顶点数和边数GraphKind kind; /图的种类 AdjListGrap遍历算法(1)深度优先遍历 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 (!vis
8、itedp-adjvex)DFS(G,p-adjvex); /当前顶点未访问，继续深度优先遍历 / DFS(2)广度优先遍历void BFS(AdjListGrap G,intv) /图 G 采用邻接表存储结构，v 是遍历起始点在邻接表中的下标，邻接表中下标从 0 开始，以队列作为基本辅助数据结构InitQueue(Q); /初始化队列 Qvisitedv=1; /置已访问标志visite(G.verticesv. vextex); /访问顶点EnQueue(Q,v); /被访问顶点入队while (!QueueEmpty(Q)DeQueue(Q,v); /出队列 for (p = G.ver
9、ticesv.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 3.函数的调用关系图mainljjzprint enqueue bfstra dfstra minispantree 4.各模块流程图及伪码算法:流程图 dfstra（1）void dfstra (MGraph *G，int i) /*以 vi 为出发点对邻接矩阵表示的图 G 进行DFS 搜
10、索，设邻接矩阵是 0,l 矩阵*/ 整型 j；打印 (visit vertex：c，G-vexsi)；/*访问顶点 vi*/visitedi=TRUE；for(j=0；jn；j+) /*依次搜索 vi的邻接点*/if(G-edgesij=1&!visitedj)DFSM(G，j)/*(v i，v j)E，且 vj未访问过，故vj为新出发点DFSM*/说明：对于具有 n 个顶点和 e 条边的无向图或有向图，遍历算法 DFSTraverse 对图中每顶点至多调用一次 DFS 或 DFSM。从 DFSTraverse 中调用DFS(或 DFSM)及 DFS(或 DFSM)内部递归调用自己的总次数为 n。当访问某顶点 vi时，DFS(或 DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为 O(n)；用邻接表表示图时，需搜索第 i 个边表上的所有结点。因此，对所有 n 个顶点访问，在邻接矩阵上共需检查 n2个矩阵元素，在邻接表
