图的操作算法

实验报告

2013—2014学年第一 学期 任课老师： 刘安丰

课程名称 Java语言与系统设计 实验名称 实验三 图的操作算法 实验环境 Dev-C++ 4.9.9.2 实验目的和内容要求 设计程序： 实现图的常用操作算法： 包括建立图的存储结构、深度优先搜索和广度优先搜索，求图的最小生成树、拓扑排序、最短路径等 实验过程记录 （1） 首先要建立图的存储结构，图的存储结构有两种：一种是邻接矩阵表示，这种存储方式便于判定任意两个顶点之间是否有边，便于求各个顶点的度。便于查找任一顶点的下一个邻接点或所有的邻接点，适用于边数较多的稠密图。一种是邻接表表示法，这种存储方式在边数较少的时候比较节省存储空间，便于找到任一顶点的第一个邻接点个下一个邻接点，便于得到无向图中顶点的度和有向图中顶点的出度。 班级 计科1204班 学号 0909121916 实验时间 姓名 崔姝瑶 第14周星期 四第7、8节 （2） 进行图的遍历：所谓“图的遍历”是指从图的某一个顶点出发访问图中的所有顶点，而且每个顶点都被访问一次的额过程。图的遍历分为优化深度遍历和广度遍历两种，图的深度遍历搜索类似于树的先根遍历，图的广度遍历类似于树的层次遍历。遍历的话从图的哪一个顶点开始都可以，但是最后要确认所有的顶点都已经被访问过了（程序见源代码）。 （3） 深度遍历，即从图的某个顶点出发，访问该顶点，然后依次从与这个顶点邻接的顶点出发继续实行深度优先搜索，直至所有的顶点都被访问到。若此时图中还有顶点没有被访问到，则从它们中间选取一个，重复实施深度优先搜索过程。实现深度遍历的存储结构最好是邻接表（程序见源代码）。 （4） 广度遍历，即是从某个顶点出发访问该结点，然后一次去访问与该结点相邻接的顶点，然后依次去访问这些已访问过的每个邻接顶点的邻接顶点，如此继续下去，直至图中所有的顶点都得到访问，且制备访问了一次。 （5） 求最小生成树的算法有两种：一个是普里姆算法，一个是克鲁斯卡尔算法。 （6） 求图的最短路径一般采用邻接矩阵的存储方式。要用几个数组来说明每个顶点的性质，dist【】存放当前找到的从源点v0到每个终点的最短路径的长度，其初态为图中直接路径权值。数组path【】表示从v0到各终点的最短路径上，此顶点的前一顶点的序号：若从v0到某终点无路径，则用0作为其前一项点的序号。数组S【】的值用来说明这个元素是不是在s集合中。(程序见源代码) （7） 最后要将最短路径输出，可以建立一个变量next用来指向数组path【】中的前一个顶点，然后逆向输出。 实验结果分析与总结 1、程序运行结果（请提供所完成的各道题运行结果界面截图）： （1）输入数据 （2）存储矩阵 （3）图的最短路径 （4）深度搜索 （5）广度搜索的输出结果 (6)拓扑排序的运行结果：