数据结构实践项目——最短路径和拓扑序列

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构实践项目——最短路径和拓扑序列

贺利坚 2015-11-15 10:11:00 浏览711
展开阅读全文

本文是针对[数据结构基础系列(7):图]的第2组实践例程。

(程序中graph.h是图存储结构的“算法库”中的头文件,详情请单击链接…

0710 生成树的概念
0711 最小生成树的普里姆算法
0712 最小生成树的克鲁斯卡尔算法
0713 从一个顶点到其余各顶点的最短路径
0714 每对顶点之间的最短路径
0715 拓扑排序
0716 AOE网与关键路径

纸上谈兵:“知原理”检验题目

1、针对下面的图1:
这里写图片描述(图1)
(1)写出图的邻接矩阵;
(2)按照Prim算法的思想,构造出最小生成树;
(3)对照Prim算法的实现,以上图作为参数g的值,用“画一画”的路线,走一遍算法,画出lowest[]和closest[]两个辅助数组的变化过程,“观察”算法执行的过程,从而达到掌握算法的目的;
(4)按照Kruskal算法的思想,构造出最小生成树;
(5)对照Kruskal算法的实现,以上图作为参数g的值,用“画一画”的路线,走一遍算法,画出E[]和vest[]两个辅助数组的变化过程,“观察”算法执行的过程,达到掌握算法的目的;
2、针对下面的图2
这里写图片描述(图2)
(1)写出图的邻接矩阵;
(2)按照Dijkstra算法的步骤,求出从顶点0到其余所有顶点的最短路径;
3、某乡有A、B、C、D四个村庄,图3中标识了各村之间的距离。现在要在某村庄修建中心俱乐部,请采用Floyd算法
这里写图片描述(图3)
(1)求出各村庄之间的最短路径;
(2)俱乐部的选址,应该使各村到俱乐部的距离之和最小,该选哪个村?
(3)写出各村到中心俱乐部的路径和路径长度。
4、针对下面的图4,尽可能多地写出其拓扑序列
这里写图片描述(图4)

上机实践

【项目 - 验证算法】运行并本周视频中所讲过的算法,观察结果并领会算法。
(1)Prim算法的验证(使用图1作为测试用例)
(2)Kruskal算法的验证(使用图1作为测试用例)
这里写图片描述(图1)
[参考解答: (1) (2)]

(3)Dijkstra算法的验证(使用图2作为测试用例)
这里写图片描述(图2)
[参考解答 ]

(4)Floyd算法验证(使用图3作为测试用例)
这里写图片描述(图3)
[参考解答 ]

(5)拓扑排序算法验证(使用图4作为测试用例)
这里写图片描述(图4)
[参考解答 ]

网友评论

登录后评论
0/500
评论
贺利坚
+ 关注