图的深度广度遍历(算法与数据结构课程设计)

《图的深度广度遍历(算法与数据结构课程设计)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。

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

4、先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。五、模块划分一、基于邻接矩阵的深广度遍历1．StatusInitQueue(LinkQueue*Q)根据已知Q初始化队列2．StatusQueueEmpty(LinkQueueQ)判断队列是否为空3．StatusEnQueue(LinkQueue*Q,QElemTypee)将e压入队尾4．StatusDeQueue(LinkQueue*Q,QElemType*e)取队头

5、元素e5．intLocateVex(MGraphG,VertexTypev)定位定点v6．voidCreateGraph(MGraph*G)建立无向图的邻接矩阵7．voidPrintGraph(MGraphG)输出邻接矩阵的无向图8．intFirstAdjVex(MGraphG,intv)第一个邻接点的定位9．intNextAdjVex(MGraphG,intv,intw)查找下一个邻接点wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/181023180210．voidDfs(MGraphG,intv)实现图的一次遍历

6、11．voidDfsTraverse(MGraphG)实现图的深度遍历12．voidBfsTraverse(MGraphG)实现图的广度遍历13．Main主函数二、基于邻接表实现图的深广度遍历1．StatusInitQueue(LinkQueue*Q)根据已知Q初始化队列2．StatusQueueEmpty(LinkQueueQ)判断队列是否为空3．StatusEnQueue(LinkQueue*Q,QElemTypee)将e压入队尾4．StatusDeQueue(LinkQueue*Q,QElemType*e)取队头元素e5．voidcreateALGraph

7、(ALGraph*G)建立无向图的邻接矩阵6．voidPrintGraph(MGraphG)输出邻接矩阵的无向图7．intFirstAdjVex(MGraphG,intv)第一个邻接点的定位8．intNextAdjVex(MGraphG,intv,intw)查找下一个邻接点9．voidDfs(MGraphG,intv)实现图的一次深度遍历10．voidDfsTraverse(MGraphG)实现图的深度遍历11．voidBFS(ALGraphG,intv)实现图的一次广度遍历12．voidBfsTraverse(MGraphG)实现图的广度遍历13．Void……

8、……………………………M