Xidian UniversityXidian University1 1图论相关算法图论相关算法第四次上机作业第四次上机作业上机时间：上机时间：2011-12-62011-12-6 晚上晚上 E-208E-208 西安电子科技大学西安电子科技大学 理学院理学院 angxidian.edu.cnangxidian.edu.cnXidian UniversityXidian University2 2实验目的实验目的n n熟悉图的概念熟悉图的概念n n熟悉图的矩阵表达熟悉图的矩阵表达n n练习最小生成树算法练习最小生成树算法PrimPrim算法算法n n练习拓扑排序算法练习拓扑排序算法n n练习关键路径算法练习关键路径算法n n练习最短路算法练习最短路算法DijkstraDijkstra和和FloydFloyd算算 法法Xidian UniversityXidian University3 3上机作业上机作业n n用用WordWord或绘图工具或或绘图工具或VisioVisio绘制待处理的连通图绘制待处理的连通图 至少至少1010个顶点个顶点3030条边，每个顶点进行编号，每条边编条边，每个顶点进行编号，每条边编 号并标明权的大小号并标明权的大小 显示该图的矩阵存储模式显示该图的矩阵存储模式n n编程完成相关算法编程完成相关算法n n绘制出该图的最终执行结果效果图绘制出该图的最终执行结果效果图 最小生成树最小生成树 关键路径关键路径 DijkstraDijkstra算法的路径算法的路径编程要求编程要求n n从下面的算法任选一个或两个从下面的算法任选一个或两个 PrimPrim算法算法+Dijkstra+Dijkstra算法算法 DijkstraDijkstra算法算法+Floyd +Floyd 算法算法 关键路径算法关键路径算法Xidian UniversityXidian University4 4Prim Prim 算法程序输出中间结果算法程序输出中间结果n n图的邻接矩阵图的邻接矩阵n n添加顶点和边的过程添加顶点和边的过程n n打印最终所有的边集打印最终所有的边集Xidian UniversityXidian University5 5关键路径算法程序输出中间结果关键路径算法程序输出中间结果n n图的邻接矩阵图的邻接矩阵n n拓扑排序结果拓扑排序结果n n每个活动的最终开工时间和最晚开工时间每个活动的最终开工时间和最晚开工时间n n每个事件的最早发生事件和最晚发生时间每个事件的最早发生事件和最晚发生时间n n关键路径关键路径Xidian UniversityXidian University6 6DijkstraDijkstra算法中间结果算法中间结果n n邻接矩阵邻接矩阵n n加入顶点和边的过程加入顶点和边的过程n n打印所有最短路径及路径的长度打印所有最短路径及路径的长度Xidian UniversityXidian University7 7FloydFloyd算法程序中间结果算法程序中间结果n n邻接矩阵邻接矩阵n n路径优化过程路径优化过程n n最后的最短路径权值最后的最短路径权值Xidian UniversityXidian University8 8其它说明其它说明n n为了打印的方便，边的权值不要超过为了打印的方便，边的权值不要超过9999n n邻接矩阵中对角线元素的表示邻接矩阵中对角线元素的表示n nDijkstraDijkstra算法和算法和Floyd Floyd 算法结果比较算法结果比较n nPrim Prim 算法和算法和DijkstraDijkstra算法过程差异比较算法过程差异比较Xidian UniversityXidian University9 9