图的深度广度遍历算法及数据结构课程设计报告

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

1、.-图的操作一、问题描述图是一种较线性表和树更为复杂的数据构造。在图形构造中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储构造下，完成图的深度、广度遍历。二、根本要求1、选择适宜的存储构造完成图的建立；2、建立图的邻接矩阵，能按矩阵方式输出图，并在此根底上，完成图的深度和广度遍历，输出遍历序列；3、建立图的邻接表，并在此根底上，完成图的深度和广度遍历，输出遍历序列；三、测试数据四、算法思想1、邻接矩阵顶点向量的存储。用两个数组分别存储数据〔定点〕的信息和数据元素之间的关系〔边或弧〕的信息。-.word.zl.-2、邻接表邻接表

2、是图的一种链式存储构造。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域〔adjvex〕指示与定点vi邻接的点在图中的位置，链域〔nextarc〕指示下一条边或弧的节点；数据域〔info〕存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域〔firstarc〕指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域〔data〕。3、图的深度遍历深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，那么深度优先搜索可从图中某个顶点v出发

3、，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；假设此时图有顶点未被访问，那么另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。4、图的广度遍历广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点〞先与“后被访问的顶点的邻接点〞被访问，直至图中所有已被访问的顶点的邻接点都被访问到。假设此时图有顶点未被访问，那么另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点

4、都被访问到为止。五、模块划分一、基于邻接矩阵的深广度遍历-.word.zl.-1．StatusInitQueue(LinkQueue*Q)根据Q初始化队列2．StatusQueueEmpty(LinkQueueQ)判断队列是否为空3．StatusEnQueue(LinkQueue*Q,QElemTypee)将e压入队尾4．StatusDeQueue(LinkQueue*Q,QElemType*e)取队头元素e5．intLocateVex(MGraphG,VertexTypev)定位定点v6．voidCreateGraph(MGraph*G)建立无向图的邻接矩阵7．voidPrintGraph(

5、MGraphG)输出邻接矩阵的无向图8．intFirstAdjVex(MGraphG,intv)第一个邻接点的定位9．intNextAdjVex(MGraphG,intv,intw)查找下一个邻接点10．voidDfs(MGraphG,intv)实现图的一次遍历11．voidDfsTraverse(MGraphG)实现图的深度遍历-.word.zl.-12．voidBfsTraverse(MGraphG)实现图的广度遍历13．Main主函数二、基于邻接表实现图的深广度遍历1．StatusInitQueue(LinkQueue*Q)根据Q初始化队列2．StatusQueueEmpty(LinkQ

6、ueueQ)判断队列是否为空3．StatusEnQueue(LinkQueue*Q,QElemTypee)将e压入队尾4．StatusDeQueue(LinkQueue*Q,QElemType*e)取队头元素e5．voidcreateALGraph(ALGraph*G)建立无向图的邻接矩阵6．voidPrintGraph(MGraphG)输出邻接矩阵的无向图7．intFirstAdjVex(MGraphG,intv)第一个邻接点的定位8．intNextAdjVex(MGraphG,intv,intw)查找下一个邻接点9．voidDfs(MGraphG,intv)-.word.zl.-实现图的一

7、次深度遍历10．voidDfsTraverse(MGraphG)实现图的深度遍历11．voidBFS(ALGraphG,intv)实现图的一次广度遍历12．voidBfsTraverse(MGraphG)实现图的广度遍历13．Void…………………………………Main主函数六、数据构造//(ADT)1、基于邻接矩阵的图的类型定义typedefstructArcCell{VRTypeadj;/*图中