数据结构 图的基本操作实现.doc

《数据结构 图的基本操作实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验五图的遍历及其应用实现一、实验目的1．熟悉图常用的存储结构。2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。3．会用图的遍历解决简单的实际问题。二、实验内容[题目一]：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列.试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。12534提示：输入示例上图的顶点和边的信息输入数据为：　57DG　ABCDE　ABAEBCCDDADBEC[题目二]：在图G中求一条从顶点i到

2、顶点s的简单路径[题目三]：寻求最佳旅游线路（ACM训练题）在一个旅游交通网中，判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路，为节省费用，不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。输入：第一行：n//n-旅游城市个数第2行：ABs1s2//s1,s2-金额数第3行---第e+2行(1≤e≤n(n-1)/2)表示城市x,y之间的旅行费用，输入000表示结束。输出：第一行表示A到B的旅游线路景点序列第二行表示沿此线路，从A到B的旅游费用设计要求：1、上机前，认真学习教材，熟练掌握图的构造和遍历算法,图的存储结构也可使用邻接矩阵等

3、其他结构.2、上机前，认真独立地写出本次程序清单，流程图。图的构造和遍历算法分别参阅讲义和参考教材事例图的存储结构定义参考教材相关函数声明：1、/*输入图的顶点和边的信息,建立图*/voidCreateGraph(MGraph&G)2、/*深度优先搜索遍历图*/voidDFSTraverse(GraphG,intv)3、/*广度优先搜索遍历图*/voidBFSTraverse(GraphG,intv)4、4、/*其他相关函数*/……三、实验步骤㈠、数据结构与核心算法的设计描述㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结四

4、、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）