数据结构课程 第十一周 图的应用

最小生成树

生成树

71.png 72.png

最小生成树

73.png 74.png 75.png 76.png 77.png 78.png

最小生成树可能不唯一

79.png

最短路径

80.png 81.png

1一个顶点到其他顶点的最短路径算法

82.png

所有顶点间最短路径
1对每个顶点重复算法1
2Floyd算法 O(n³)

83.png 84.png

拓扑排序

85.png 86.png

AOV解决拓扑排序；AOE解决关键路径

87.png 88.png 89.png 90.png 91.png

关键路径

用AOE网表示关键路径

92.png 93.png 94.png

求解关键路径

95.png 96.png 97.png 98.png

最早发生时间（左）和最晚发生时间（右）举例：

99.png 100.png

ve是顶点i的最早发生时间，当有多个入口时，选和最大的一条（类似课程，需要把基础都学完才能学下一门）
vl是顶点i的最晚发生时间，算完所有的ve后，从终点往回算，如上面从18开始往回推，（如果要在第18天完成，则上一条最晚在多少天开始学，当有多个来源时取最小的）
e是活动最早开始时间。（理解：把之前基础课都学完才能学下一门，所以有多条入口时，是取得最大的，也就是ve）
l代表最晚什么时候开始学才能赶上最终进度。

l-e = 0的为关键节点（一天也晚不了）从而求出关键路径！！！

101.png