中国科学技术大学UniversityofSeienceandTechnologyfChin算法基础上机实验4育创银牌学 期：2016（秋)清通
算法基础 上机实验 4 学 期: 2016 (秋)
Sohoolof CSTAIVERSITYCIENCE&TECOHBCHINAProject4:图论算法实验1：实现求有向图的强连通分量的算法。有向图的顶点数N的取值分别为：9、27、81、243、729，弧的数目为Nlog3N，随机生成Nlog3N条弧，统计算法所需运行时间，画出时间曲线。实验2：实现求所有点对最短路径的Floyd-Warshall算法。有向图的顶点数N的取值分别为：9、27、81、243、729，弧的数目为Nlog3N，随机生成Nlog3N条弧，统计算法所需运行时间，画出时间曲线
School of CST Project 4: 图论算法 ◼ 实验1：实现求有向图的强连通分量的算法。有向图的顶点数 N 的取值分别为： 9、27、81、243、729， 弧 的数目为 Nlog3N, 随机生成 Nlog3N 条弧，统计算法所需运行时间 ， 画出时间曲线。 ◼ 实验2：实现求所有点对最短路径的Floyd-Warshall算法。有向 图的顶点数 N 的取值分别为: 9、27、81、243、729 ， 弧的 数目为 Nlog3N, 随机生成 Nlog3N 条弧，统计算法所需运行 时间 ，画出时间曲线
Sohoolof CSTNVERSITTFSCIENCE&TECHNOLOCYOFCHINA实验要求1、输入输出格式：■a)两个实验分别建立project1，project2文件夹，每个文件夹分别包含3个文件夹：Input文件夹：存放输入的图的数据Source文件夹：源程序Output文件夹：输出信息b)input实验一：为每种输入规模分别建立一个子文件夹，实验数据规模从小到大分别为size1,size2,size3,size4,size5,随机生成的有向图信息分别存放到对应数据规模文件夹里面的input.txt文件，每行存放一对节点i，序号（数字表示），表示存在一条节点i指向节点的边。分别读取这五个规模的图数据进行求解最强连通分量的实验.实验二：同实验一为每种输入规模分别建立一个子文件夹，随机生成边上的权值，权值范围统一在（-10,30）之间。随机生成的有向图分别存放到对应数据规模文件夹里面的input.txt文件，每行存放一对节点i,序号，表示这两个节点之间存在着一条边相连，以及边的权值のi。分别读取这五个规模的图数据进行求解所有点对最短路径的实验C)output:为每种数据规模建立一个子文件夹，分别为size1,size2,size3,size4,size5其输出结果数据导出到其对应子文件下面.output1.txt：输出对应规模图中存在的所有连通分量■time1.txt：输出测试求解出每个连通分量所花费的时间。第二个实验输出结果同样是导入到相同的对应子文件夹下面output2.txt：输出对应规模图中所有点对之间的最短路径包含的节点序列及路径长。time2.txt：输出测试程序求解出对应规模图所有点对最短路径所消耗的时间
School of CST 实验要求 1、输入输出格式: ◼ 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: 输出测试程序求解出对应规模图所有点对最短路径所消耗的时间
Sohoolof CSTANVERSLTYSCIENCE&TECHNOLOCYOFCHINA实验要求2、实验细节■a)进行算法实现时选取合适的数据结构和实现方法来表示图。b)实验一中输出的连通分量数据要表示清楚，同一个连通分量的节点序列用一对括号括起来输出到output.txt文件中，如果可以实现图形化显示每个连通分量并正确清楚的表示出来可以给予加分。C)实验二中输出的最短路径要表示清楚，在一条最短路径的节点序列用一对括号括起来输出到output.txt文件中，并输出路径的长度。d)实验二中随机生成边以及权值，实验首先应判断输入图是否包含一个权重为负值的环路，如果存在，则对输入图的边以及权值重新随机生成以保证实验正确进行■e)针对书上给的算法能够进行部分改进或创新并正确实现的，可以给予加分
School of CST 实验要求 2、实验细节 ◼ a)进行算法实现时选取合适的数据结构和实现方法来表示图。 ◼ b)实验一中输出的连通分量数据要表示清楚，同一个连通分量的节点序列 用一对括号括起来输出到output.txt文件中，如果可以实现图形化显示每个 连通分量并正确清楚的表示出来可以给予加分。 ◼ c)实验二中输出的最短路径要表示清楚，在一条最短路径的节点序列用一 对括号括起来输出到output.txt文件中，并输出路径的长度。 ◼ d)实验二中随机生成边以及权值，实验首先应判断输入图是否包含一个权重为负 值的环路，如果存在，则对输入图的边以及权值重新随机生成以保证实验正确进行 。 ◼ e)针对书上给的算法能够进行部分改进或创新并正确实现的，可以给予加 分
Sohoolof CSTNYERSUTOYSCIENCE&TECHNOLOGYOCHINA实验要求4、性能测试a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参考project1给出的图表式样；b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图，比较不同规模下时间曲线变化规律的异同，给出分析
School of CST 实验要求 4、性能测试 ◼a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参 考project1给出的图表式样； ◼b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时 间曲线图,比较不同规模下时间曲线变化规律的异同，给出分析