算法基础 上机实验 4 学 期: 2017 (秋)
Project 4: 图论算法 实验1：实现求有向图的强连通分量的算法。有向图的顶点数 N 的取值分别为：8、16、32、64, 128、256， 弧的数目为 NlogN, 随机生成 NlogN条弧，统计算法所需运行时间 ，画出时间曲线。 实验2：实现求所有点对最短路径的Johnson算法。生成连通的无向图，图的顶点数 N 的取值分别为： 8、16、32、64, 128、256 ， 边的数目为 NlogN, 随机生成 NlogN 条边，统计算法所需运行时间 ，画出时间曲线。 2
Project 4: 图论算法 补充说明：实验4中第二题随机生成的边的权值加两个条件。1. 1/n的边的权值为负的，且绝对值不大于log n。 2. 剩余的边权值为正，且不大于n。 如果万一随机生成的图出现圈且圈的边权值总和小于0的情况，请重新生成一个。 3
实验要求 1、输入输出格式: c)output： a)两个实验分别建立project1，project2文件夹，每个文件夹分别包含3个文件夹： Input文件夹： 存放输入的图的数据 Source文件夹：源程序 Output文件夹：输出信息 b)input 实验一：为每种输入规模分别建立一个子文件夹，实验数据规模从小到大分别为size1,size2,size3,size4,size5,size6,随机生成的有向图信息分别存放到对应数据规 模文件夹里面的input.txt文件，每行存放一对节点a,b序号(数字表示)，表示存在一条节点a指向节点b的边。分别读取这五个规模的图数据进行求解最强连通分量的实验. 实验二：同实验一为每种输入规模分别建立一个子文件夹,随机生成的无向图息分别存放到对应数据规模文件夹里面的input.txt文件，每行存放一对节点a,b序号，表示这两个节点之间存在着一条边相连。分别读取这五个规模的图数据进行求解所有点对最短路径的实验. c)output： 为每种数据规模建立一个子文件夹，分别为size1,size2,size3,size4,size5,size6其输出结 果数据导出到其对应子文件下面 output1.txt ：输出对应规模图中存在的所有连通分量 time1.txt：输出测试求解出每个连通分量所花费的时间。 第二个实验输出结果同样是导入到相同的对应子文件夹下面 output2.txt :输出对应规模图中所有点对之间的最短路径包含的节点序列及路径长。 time2.txt: 输出测试程序求解出对应规模图所有点对最短路径所消耗的时间。
实验要求 2、实验细节 a)进行算法实现时选取合适的数据结构和实现方法来表示图。 b)实验一中输出的连通分量数据要表示清楚，同一个连通分量的节点序列 用一对括号括起来输出到output.txt文件中，如果可以实现图形化显示每个 连通分量并正确清楚的表示出来可以给予加分。 c)实验一中输出的最短路径要表示清楚，在一条最短路径的节点序列用一对括号括起来输出到output.txt文件中，并输出路径的长度。 d)针对书上给的算法能够进行部分改进或创新并正确实现的，可以给予加分。
实验要求 4、性能测试 a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参考实验一给出的图表式样； b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图,比较不同规模下时间曲线变化规律的异同，给出分析.
实验要求 5、注意事项 a) 实验报告中要有必要的实验过程截图和图表 b) project目录结构严格按照输入输出格式的要求； d) 实验杜绝抄袭他人代码或者实验结果，如发现代码高度相似或者实验报告雷同者算0分； e) 实验报告格式参照project1； f) 实验报告请严格按照“学号-姓名-project1.rar”的方式上传到ftp服务器； g) 实验截止时间：1月7号 24:00