图的遍历的数据结构课程设计

《图的遍历的数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的深度遍历和广度遍历学生姓名：指导老师：肖增良摘要：数据结构是一门专业基础课，学习数据结构要求我们学会研究计算机加工的数据结构特性，以便为应用涉及的数据结构选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的的技术,图是应用最广泛的数学结构。图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。对于广度优先遍历应利用队列的五种基

2、本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。关键词图遍历深度广度队列算法目录1.课程设计的要求……………………………………………………………………32.设计方案……………………………………………………………………………42.1图的初始化……………………………………………………………………42.2深度优先搜索的基本思想……………………………………………………42.3广度优先搜索的基本思想…………………

3、…………………………………62.4图的深度优先搜索和广度优先搜索的定义…………………………………73.图的遍历模块化……………………………………………………………………83.1图的存储结构…………………………………………………………………83.2邻接表的定义和初始化………………………………………………………93.3BDF和DBF编码………………………………………………………………104．图的遍历流程图……………………………………………………………………134.2图的深度优先遍历流程………………………………………………………134.2图的广度优先遍历流程图……

4、………………………………………………145．系统运行运行环境与结果…………………………………………………………155.1运行环境………………………………………………………………………155.2结构图图及运行结果…………………………………………………………166．课程设计总结………………………………………………………………………17参考文献……………………………………………………………………………18附录：源程序代码…………………………………………………………………191课程设计的要求该课题要求我们熟悉图，图是一种较为线性表和树更为复杂的数据结构。在线性表中，

5、数据元素之间仅有线性关系，每一个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子结点）有关，但只能和上一层中一个元素（即双亲结点）有关；而在图形结构中，节点之间的的关系是任意的，图中任意两个数据元素之间都可能相关。图的应用极为广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及其他的分支中。图的遍历算法是求解图的连通性问题、拓扑排序和求解关键路径等算法的基础。而深度遍历优先搜索和广度遍历优先搜索是遍历图的最基本的两条途径。因

6、此，本课程要求我们能熟练地掌握深度优先搜索遍历和广度优先搜索遍历的方法对图进行搜索。2设计方案2.1图的初始化typedefVertexNodeAdjList[MaxVertexNum];/*AdjList是邻接表类typedefstructnode{/*边表结点*/intadjvex;/*邻接点域*/structnode*next;/*链域*/}EdgeNode;typedefstructvnode{/*顶点表结点*/charvertex;/*顶点域*/EdgeNode*firstedge;/*边表头指针*/}VertexNode;型*/typedefst

7、ruct{AdjListadjlist;/*邻接表*/intn,e;/*图中当前顶点数和边数*/}ALGraph;/*图类型*/2.2深度优先搜索的基本思想深度优先搜索是一种递归的过程，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。   假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点

8、)均已被访问为止。若此时图中仍有未访问的顶点，则另选