资源描述：
《实验四：图地深度优先与广度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实用文档实验报告学院（系）名称：计算机与通信工程学院姓名**学号********专业计算机科学与技术班级2015级*班实验项目实验四：图的深度优先与广度优先遍历课程名称数据结构与算法课程代码0661013实验时间2017年5月12日第5-6节实验地点7-216考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○内容极少○无报告○有○无○有○无文案大全实用文档一
2、、实验目的理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法二、实验题目与要求1.每位同学按下述要求实现相应算法：根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph():按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图3）实验提示:²图的存储可采用邻接表或邻接矩阵；
3、²图存储数据类型定义（邻接表存储）#defineMAX_VERTEX_NUM8//顶点最大个数typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;//边的权}ArcNode;//表结点#defineVertexTypeint//顶点元素类型typedefstructVNode{intdegree,indegree;//顶点的度，入度VertexTypedata;文案大全实用文档ArcNode*firstarc;}Vnode/*头结点*/;typedefstruct{Vnodevertices[MAX_VERTEX_NUM
4、];intvexnum,arcnum;//顶点的实际数，边的实际数}ALGraph;4）注意问题:²注意理解各算法实现时所采用的存储结构。²注意区别正、逆邻接。2.拓扑排序：给出一个图的结构，输出其拓扑排序序列（顶点序列用空格隔开），要求在同等条件下，编号小的顶点在前。3．利用最小生成树算法解决通信网的总造价最低问题1）问题描述：若在n个城市之间建通信网络，架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。2）实验要求：利用Prim算法求网的最小生成树。3)实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点数
5、不超过10个，网中边的权值设置成小于100。三、实验过程与实验结果应包括如下主要内容：Ø数据结构定义Ø图是由定点集合及定点间的关系集合组成的一种数据结构，其形式化定义为Graph=（V，E）其中，V={x
6、x∈某个数据对象}是定点的有限非空集合；E={（x,y）
7、x,y∈V∧Path(x,y)}是顶点之间关系的有限集合，叫做便集。集合E中的Path（x,y）表示顶点x和顶点y之间有一条直接连线，即（x,y）表示一条边，它是有方向的。Ø算法设计思路简介ØØ算法描述：可以用自然语言、伪代码或流程图等方式Ø1、Ø图的深度优先搜索：Ø在访问图中某一起始点V后，由V出发，访问它的任一邻接顶点w1;再从w
8、1；出发，访问与w1邻接但还没有访问过得顶点w2；然后再从w2出发，进行类似的访问，…,如此文案大全实用文档进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止；接着退回一步，回溯到u的前一个邻接顶点，看它是否还有其他没有被访问过的邻接点。如果有，则访问此邻接点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直至图中所有和V连通的顶点都被访问到。若此时图中尚有顶点未被访问，则说明该图不是连通图，另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问过为止。Ø图的广度优先搜索：Ø使用广度优先搜索（BFS）在访问了起始顶点V之后，由
9、V出发，依次访问V的各个未曾被访问过的邻接点w1,w2,…,wt,然后再顺序访问w1,w2,…,wt，的所有还为访问过的邻接点。再从这些顶点出发，访问它们还未访问过的邻接点，…，如此做下去，直到图中所有顶点都被访问过为止。Ø2、Ø（1）将没有前驱（入度为零）的顶点进栈。Ø（2）从栈中退出栈顶元素输出，并把该顶点引出的所有弧删去，即把它的各个邻接点的入度减1，同时将当前已输出的顶点个数加1.Ø（3）
