算法基础 上机实验 4 学 期: 2016 (秋)
Project 4: 图论算法 实验1：实现求有向图的强连通分量的算法。有向图的顶点数 N 的取值分别为： 9、27、81、243、729， 弧 的数目为 N log 3 N, 随机生成 N log 3 N 条弧，统计算法所需运行时间 ，画出时间曲线。 实验2：实现求所有点对最短路径的Floyd-Warshall算法。有向图的顶点数 N 的取值分别为: 9、27、81、243、729 ， 弧的数目为 N log 3 N, 随机生成 N log 3 N 条弧，统计算法所需运行时间 ，画出时间曲线。 2
实验要求 1、输入输出格式: c)output： a)两个实验分别建立project1，project2文件夹，每个文件夹分别包含3个文件夹： Input文件夹： 存放输入的图的数据 Source文件夹：源程序 Output文件夹：输出信息 b)input 实验一：为每种输入规模分别建立一个子文件夹，实验数据规模从小到大分别为size1,size2,size3,size4,size5,随机生成的有向图信息分别存放到对应数据规 模文件夹里面的input.txt文件，每行存放一对节点i,j序号(数字表示)，表示存在一条节点i指向节点j的边。分别读取这五个规模的图数据进行求解最强连通分量的实验. 实验二：同实验一为每种输入规模分别建立一个子文件夹,随机生成边上的权值，权值范围统一在（-10,30）之间。随机生成的有向图分别存放到对应数据规模文件夹里面的input.txt文件，每行存放一对节点i,j序号，表示这两个节点之间存在着一条边相连,以及边的权值 ω 𝑖𝑗 。分别读取这五个规模的图数据进行求解所有点对最短路径的实验. c)output： 为每种数据规模建立一个子文件夹，分别为size1,size2,size3,size4,size5其输出结 果数据导出到其对应子文件下面 output1.txt ：输出对应规模图中存在的所有连通分量 time1.txt：输出测试求解出每个连通分量所花费的时间。 第二个实验输出结果同样是导入到相同的对应子文件夹下面 output2.txt :输出对应规模图中所有点对之间的最短路径包含的节点序列及路径长。 time2.txt: 输出测试程序求解出对应规模图所有点对最短路径所消耗的时间。
实验要求 2、实验细节 a)进行算法实现时选取合适的数据结构和实现方法来表示图。 b)实验一中输出的连通分量数据要表示清楚，同一个连通分量的节点序列 用一对括号括起来输出到output.txt文件中，如果可以实现图形化显示每个 连通分量并正确清楚的表示出来可以给予加分。 c)实验二中输出的最短路径要表示清楚，在一条最短路径的节点序列用一对括号括起来输出到output.txt文件中，并输出路径的长度。 d)实验二中随机生成边以及权值，实验首先应判断输入图是否包含一个权重为负值的环路，如果存在，则对输入图的边以及权值重新随机生成以保证实验正确进行。 e)针对书上给的算法能够进行部分改进或创新并正确实现的，可以给予加分。
实验要求 4、性能测试 a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参考project1给出的图表式样； b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图,比较不同规模下时间曲线变化规律的异同，给出分析.
实验要求 5、注意事项 g)如果有同学在截止日期前要重复提交，邮件主题需说明重复提交； h) 第四次实验截止时间：12月21号 24:00 a) 实验报告中要有必要的实验过程截图和图表； b) project目录结构严格按照输入输出格式的要求； c) 代码要注意规范性，算法关键实现的地方给出必要的注释； d) 实验杜绝抄袭他人代码或者实验结果，如发现代码高度相似或者实验报告雷同者算0分； e) 实验报告格式参照project1； f) 实验报告请严格按照“学号-姓名-project4.rar”的格式打包成.rar格式上传到ncaa_lab508@126.com邮箱； g)如果有同学在截止日期前要重复提交，邮件主题需说明重复提交； h) 第四次实验截止时间：12月21号 24:00