实验五 图的遍历

《实验五 图的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验题目：图的遍历1．需求分析以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。①输入的形式和输入的值的范围：输入图的顶点个数和边的个数；输入每个顶点对应的值；输入每条边对应的序号。以上输入均为整形数。②输出的形式：将建立的邻接表输出；将按照深度遍历图的顺序输出结点；按照广度遍历图的顺序输出结点。③程序能达到的功能：对图建立邻接表存储，输出邻接表，并对其进行遍历（深度优先和广度优先），将遍历结果打印输出。④测试数据：顶点数：5边数：6顶点对应的值：12345每条边对应的顶点序号：（0

2、3）（01）（23）（12）（14）（24）2．算法设计本程序包含十一个函数：①主函数main②创建邻接表函数：voidCreateGraph(ALGraph&G);③广度遍历邻接表函数：voidBFSTraverse(ALGraphG,int(*Visit)(intv))④深度遍历邻接表函数：voidDFSTraverse(ALGraphG,int(*Visit)(intv))voidDFS(ALGraphG,intv)⑤intFirstAdjVex(ALGraphG,intv)⑥intNextAdjVex(ALGraphG,intv,intw)⑦

3、初始化队列函数：intInitQueue(SqQueue&queue)⑧入队列函数：intEnQueue(SqQueue&queue,intelement)⑨出队列函数：intDeQueue(SqQueue&queue,int&element)⑩判断队列是否为空函数：intQueueEmpty(SqQueuequeue)⑾访问打印结点函数：intprintGraph(intv)设计分析：图的遍历主要就有四个函数，主函数，创建邻接表函数，广度遍历函数，深度遍历函数。主函数调用其他三个函数，而这三个函数有分别调用自己实现功能的函数。例如：广度遍历函数引入

4、队列操作的函数。3．调试分析调试过程中遇到的问题是如何解决的：在编写程序的过程中出现了许多问题，下面我就简要的提一下。在编写此程序的过程中，最大的问题出创建邻接表的存储结构上，创建边结点的时候指针的指向问题没有搞清楚，边结点刚开始没有建立好，导致后面的运行错误，我后来查找了一些创建邻接表的资料，才把问题解决；再有就是FirstAdjVex与NextAdjVex函数的算法编写上也出了问题，刚开始，我想的是返回的值是一个结点类型的，在后面的算法中有好多都无法实现，后来和同学讨论后，把返回的值的类型改为整形的，返回的是结点的位置，算法就容易实现了。对设计与

5、实现的回顾讨论和分析：对于这次实验，我充分的体会到了函数的封装性，课本上有现成的算法，只是一些小的函数，没有列出，但是函数要实现的内容也都告诉我们了，所以编程的过程大大的简化了。象一些对队列的操作在前面都学习过，象FirstAdjVex(ALGraphG,intv)函数和NextAdjVex(ALGraphG,intv,intw)的实现的功能课本上也都列出了。所以编程的过程并不复杂。经验收获和体会：这次实验书上有好多现成的算法，所以要求我动脑子编程的东西并不多，但是在编程的过程中，我却感到了危机感，因为在编程过程中利用到的书上学过的现成算法，我在编程

6、过程中尝试自己写写，但是有好多都写不出来，比如说对队列的操作。这次实验虽然碰到的问题不大，但是却恰恰暴露了我的弱点，即我对于所学过的知识，并不是充分的掌握和理解了。要不不会出现对一些简单的操作算法都写不全。认识到了这个缺点，我对这次要用到的一些操作算法，进行了复习，发现了好多问题。通过编程，我巩固了过去所学的知识，巩固了目前学习的知识，同时也收获了经验。1．用户使用说明程序开始运行:请输入顶点数和边数:请输入5顶点值:请输入6条边对应的顶点的序号:——————————————按照上述提示分别输入即可。2．调试结果**********实验五图的遍历**

7、********************计科041梁爽*************程序开始运行:请输入顶点数和边数:56请输入5顶点值:12345请输入6条边对应的顶点的序号:第1条边的顶点序号:03第2条边的顶点序号:01第3条边的顶点序号:23第4条边的顶点序号:12第5条边的顶点序号:14第6条边的顶点序号:24输出邻接表如下:01--->1--->312--->4--->2--->023--->4--->1--->334--->2--->045--->2--->1输出深度:12534输出广度:12453Pressanykeytocontinue

8、1．附录#include#include#include