实验五 图的基本操作.doc

《实验五 图的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容本次实验提供两个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其他选做！题目一：图的遍历（必做）[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。[测试数据]由学生依据软件工程的测试技术自己确定。题目二：在图G中求一条从顶点i到顶点s的简单路径[测试数据]自行设计题目三：在图G中求一条

2、从顶点i到顶点s且长度为K的简单路径[测试数据]自行设计三、算法设计1、主要思想：首先定义邻接表存储结构，然后创建一个空队列，进行队列的进队，出对和判空操作，然后建立邻接表，接着进行图的深度优先遍历和广度遍历，最后编写主函数。对于邻接表，是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息。每个链表上附设一个表头结点。infonextarcadjve

3、x表结点：firstarcdata头结点：对于图的深度优先遍历DFS，类似于树的先根遍历，是树的先跟遍历的推广，是一个递归算法；对于图的广度优先遍历BFS，类似于树的层次遍历，不是递归算法。1、本程序包含6个模块（1）主函数voidmain(){定义图，输出图的深度优先遍历和广度优先遍历结果；}（2）队列的构造：包括队列的初始化、进队、出对和判空，intInitQueue（）；intEnQueue（）；intDeQueue（）；intQueueEmpty（）。（3）邻接表的建立voidGreatGraph（）；（4）图的深度优先遍历voidDFS（）；（5）图的广度优先遍历v

4、oidBFS（）；2、元素类型和结点类型typedefstructArcNode{intadjvex;structArcNode*nextarc;intinfo;}ArcNode;typedefstructVNode{chardate;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;typedefstructQNode{chardata;structQNode*next;}QNode,*QueuePtr;typedef

5、struct{//构造一个空队列QueuePtrfront;QueuePtrrear;}LinkQueue;3、主函数和其他函数清单（1）intInitQueue（）：初始化队列；（2）intEnQueue（）：进队；（3）intDeQueue（）：出对；（4）intQueueEmpty（）：队列的判空（5）voidGreatGraph（）：建立邻接表；（6）voidDFS（）：深度优先遍历；（7）voidBFS（）：广度优先遍历；（8）voidmain（）：主函数。一、调试分析算法设计欠周全，在编写输出两条边的信息的时候，不能一次性输入完毕，必须得输入两个顶点后才能接着输入

6、下一顶点信息，比较繁琐，不够简洁，如果顶点够多的话，比较花费时间；对输入的数据有了一定的考虑，如果输入的数据不合理，也就不能正确输出；刚开始时给数据赋初值有错，以后的多注意。一、实验结果利用课本第168页图7.13（a）图的数据进行测试二、总结对于这次实验，心里面一直很担心，因为实验都快做完了，我还一次都没有让老师检查过，然后时间上有特别的紧张，知道要做实验了，就一遍又一遍的去看书上相关的算法，上网查询，还有问了别的同学，最后才勉勉强强的将它给弄出来了。在让老师检查的时候，特别的紧张，话都说不利索了，很开心，但是还是有很多的不足之处，还是得好好的多看书，把基础知识给弄透彻。我

7、争取下次还把实验给做出来。一、源程序#include#include#include#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;structArcNode*nextarc;intinfo;}ArcNode;typedefstructVNode{chardate;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruc