发布时间 : 星期六 文章2014数据结构实验指导书 doc更新完毕开始阅读
3、熟悉构造最小生成树的Prim算法； 4、单源最短路径的Dijkstra算法。
【实验原理】
图是一种比树更为复杂的数据结构。图的逻辑结构是数据元素之间多对多的联系，在图中的每一个结点都可能和其它的结点相关联。图的应用范围十分广泛，诸如电子线路分析、系统工程、寻找最短路径、人工智能、计算机科学、化学、控制论以及社会科学等领域。相对前面的数据结构而言，图的内容比较难。
通常有两种遍历图的方法：深度优先搜索（DFS）遍历和广度优先搜索（BFS）遍历。深度优先搜索类似于树的先序遍历，是树的先序遍历的推广，是一个递归过程。广度优先遍历类似于树的按层次遍历过程。
最小生成树是用于构造连通图的最小代价生成树，在交通、通信等领域有着广泛的应用，最小生成树有着很多种算法，典型的有Prim算法和Kruskal算法。
从单个源点到其余各顶点的最短路径算法的应用比较广泛，尤其是在交通联系方面。典型的实现算法有Dijkstra算法。
【实验要求】
实验课题：
0120
24
25381 11337456 图2
2324144 图1
09
5图3
实验任务：
对图1 — 图3，实现以下操作，记录并分析相应的试验结果： ① 输出相应图的邻接矩阵；
② 输出相应图的DFS结果；
17
③ 输出相应图的BFS结果。
选做：对图3，用Dijkstra算法求出其单源最短路径。使用Prim算法求出其最小生成树。
开始 访问顶点Vi+1 开始
依次搜索Vi+1的邻接点读入n个顶点
递归访问顶点N Vj+1访问过？ 邻接矩阵初始化 Y Vi+1的邻接点都访问读入e条边
N Y 结束 结束 图4 图的邻接矩阵表示法流程图 图5 图的深度优先遍历算法流程图
参考源文件：
用C版本的同学可参考以下文件，了解其内容和具体算法的实现。
graph.h：声明了图相关函数的函数原型，graphutil.c：定义了生成和打印图的函数。剩余实现各算法的源文件命名的规律是：
开头的gr：表示图算法 bfs: Breadth First Search dfs: Width First Search dijk: Dijkstra 算法 prim: Prim 算法
l 和 m：分别表示该程序中的图是用邻接表或邻接矩阵表示的。
图的输入和gph文件的理解
在这个框架里，图用文本文件（*.gph）来描述（图的结点数目，有向图还是无向图，图中的边的描述，边是否带权值等信息），有了这样的描述文件，就可以用函数createGraph来创建图的对象。可以参考grtestm.cpp和grtestl.cpp。
创建这种文件来描述图，要注意以下规则：
1)、以“#”开头的行表示注释（文本中任意行从“#”开始到该行结束都表示注释）；
18
2)、文本文件中有效的第一行表示结点数目；
3)、文本文件中有效的第二行表示图是有向还是无向，“D”表示有向图，“U”表示无向图； 4)、文本文件中有效的第三行开始表示图中的边，每条边用一行表示；
如果是无权值图，则每行有两个数值，数值之间用空格隔开，第一个数值表示边的起始结点，第二个数值表示边的终止结点，并且第二个数值后不能再有空格或者其它数值。（注意，结点编号一定用数字表示，且编号从0开始）；
如果是带权值图，则每行有三个数值，数值之间用空格隔开，第一个数值表示边的起始结点，第二个数值表示边的终止结点，第三个数值表示边的权值。（注意，结点编号一定用数字表示，且编号从0开始）；
5)、做实验时注意先把自己需要用到的图，用该gph文件规则描述后使用；
6)、若系统中需要用到相应的图文件，则对于.net编译器，图文件的输入在“项目”菜单下的“工程名属性”栏目中的“调试”页面下的“命令参数”编辑框里填入文本图的文件名（全名）即可对该图文件进行相应的处理。
做实验时对图1 — 图3，要先创建与上面三个图对应的gph文件，分别保存为test1.gph、test2.gph和test3.gph，对格式还不熟悉的，可参考随源程序附带的*.gph文件，如bkfig91.gph文件用来存储教材中的图9.1。
19
综合设计考核
【实验目的】
通过一个实际问题的解决，来考察学生对数据结构课程算法的设计与实现的掌握程度。
【实验要求】
（实验采用C语言编程，可以使用课本提供的基本数据结构的源码） 具体实验内容由由实验指导老师决定。
【实验内容与步骤】
1根据给出实验课题，完成自己的算法设计（以书写为准）流程或方法，并编程具体实现。（可使用教材给出的相关资源代码）。 2完成后举手示意让老师验收。
3回去后完成自己的实验报告。实验报告中应有算法的分析、实现以及遇到的问题及其解决方案和实验后的心得。最后一次实验报告的时间届时通知。 4 在综合设计实验过程中严禁互相讨论交流，严禁携带资料进入。
20