最小生成树
用途：用最少的资源构建起支撑这n个节点的一张网或图
1、概念
- 生成树（要求连通但是没有回路）
- 一个图可以有许多颗不同的生成树
- 所有生成树的共同特点：
- 生成树的顶点个数与图的顶点个数相同
- 生成树是图的极小连通子图，去掉一条边则非连通
- 一个有n个顶点的连通图的生成树有n-1条边
- 在生成树中再加一条边必然形成回路
- 生成树中任意两个顶点间的路径是唯一的
- 含n个顶点n-1条边的图不一定是生成树
- 构造生成树的思路（以无向图的生成树为例）
- 利用深度优先遍历搜索得到
- 利用广度优先遍历搜索得到
- 总结
- 定义
- 应用
（n个城市最少就是n-1条路，确保连通，最多有Cn2条路）
2、MST概念
MST性质：
MST性质例子：
此时，u是顶点集v的非空子集，再V-U集合就是差集。其中，以v1为例，其和v2,v3,v4都有一条边，其中v1到v3边的权值最小，根据MST性质，就是说其一定会包含在某一颗最小生成树中。
MST性质解释
ps：如果加上了这条边会造成回路，再忽略再选取其他权值最小的边。
3、实现
- 构造最小生成树方法一：普里姆算法（Prim算法）
- 过程：
- 假设一开始v1在u集合中，而u集合此时与差集只有v1-v2/v3/v43条边，选出其中权值最短的边v1-v3，权值是1，再将v3加入u集合。
- 此时，u集合中有v1，v3两个顶点，这两个顶点与其他的顶点间权值最小的边是v3-v6，权值是4，然后将v6也加入u集合。
- 此时，u集合中有v1，v3，v6，此时与其他顶点最短的边是v6-v4，权值是2的边，所以将v4也加入u集合。
- 此时，u集合中有v1，v3，v4，v6，此时与其他顶点最短的边是v3-v2，权值是5，然后将v2也加入u集合。
- 此时，u集合中离v5最短的边是v2-v5，将最后的v5加入u集合，结束，此时所选的边加上顶点就是最小生成树。
- 构造最小生成树方法二：克鲁斯卡尔（Kruskal算法）
（将权值最小的边由小到大排序，不断的选取权值最小的边，前提是不能形成环）
（最小生成树不唯一）
- 两种算法的比较
（提示：由于Kruscal算法是按边来操作，而稀疏图的边比较少，所以适合稀疏图）
最短路径
- 用途：求两点间最短路径或某源点到其他各点最短路径
1、概念
- 问题：
- 第一类问题：两点间最短路径
可见，第二条路径最短最优
- 第二类问题：某源点到其他各点最短路径
- 实现的算法：
2、实现
Dijkstra(迪杰斯特拉)算法
单源最短路径 — Dijkstra(迪杰斯特拉)算法
实现思路：按路径长度递增次序产生最短路径
例子
分析：
- 一开始的S集合中只有v0，此时v0里其他顶点的距离如图所示，其中到达不了的设为无穷大。其中v0到v2的距离最短，为8，所以选取v2加入S集合，此后就不需要再对比到v2的距离。
- 此时S的集合中有V0，v2，再次看看有了V2顶点的加入，能不能剪短到其他顶点的距离。可见，有了v2的加入，v0可以到达v3，距离为13，最短的距离，但是v0到v1也是最短的距离。所以这一次选取v1加入S集合，此后不需要再对比v1的距离。
- 此时S的集合中有v0，v1，v2，再次看看有了v1顶点的加入，能不能剪短到其他顶点的距离。可见，有了v1的加入，v0又可以到达v5，v6，但是这次的最短距离是上次的v2到v3，所以选取v3加入S集合，此后不再需要对比v3的距离
- 此时S的集合中有v0，v1，v2，v3，再次看看有了v3顶点的加入，能不能剪短到其他顶点的距离。可见，有了v3的加入，v0又可以到达v4，切这次到达v4的距离更短，为19，比此时其他的距离都短。所以选取v4加入S集合，此后不再需要对比v4的距离.
- 此时S的集合中有v0，v1，v2，v3，v4，再次看看有了v4顶点的加入，能不能剪短到其他顶点的距离。可见，有了v4的加入，v0又可以到达v5，且这次到达v5的距离更短，为21，但是v0到v6的距离更短。所以选取v6加入S集合，此后不再需要对比v6的距离.
- 最后一次，选取v5加入S集合，此时全部的顶点都加入了S集合，算法结束。
弗洛伊德（Floyd）算法
- 所有顶点间的最短路径
方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。
方法二：弗洛伊德（Floyd）算法
- 算法思路
- 例子：
- 分析：
- 本来的路径长度如图所示。
- 加入了A顶点之后，本案例C是不能到达B的，所有距离是无穷大，但是增加了A顶点之后，C可以到达B，距离为3+4=7，所以表格的距离修改为7.
- 加入了B顶点之后，本来A去C只能是11，但是现在可以借住B来到达C，距离更短，为6.
- 加入了C顶点之后，本来B去A需要6个距离，现在借助C，2+3=5，距离更短。
- 算法结束，此时就得到了有向网中的所以顶点的最短路径。经过的顶点和路径权值如最后的表所示。
拓扑排序
用途判断AOE网中是否存在环。
1、概念
有向无环图：无环的有向图，简称DAG图
用途
AOV网与AOE网
ps：通常AOV网用来解决拓扑排序问题，而AOE网用来解决关键路径问题。
AOV网的特点
其中：
C1是C4的直接前驱，C4是C1的直接后继
C1是C5的前驱，C5是C1的后继
问题：如何判断AOV网中是否存在回路？ ---- 拓扑排序
拓扑排序的定义
2、拓扑排序的方法
例子：过程如下所示（拓扑序列不唯一）
不唯一
检测AOV网中是否存在环的方法：
否则互相存在前驱必有环。
关键路径
引子
建模（AOE网的抽象）
解析：其中的v1->v2，表示菜单定制活动开始，到v2菜单定制活动结束，花费的时间A=20分钟。其他同理。
建模二
将问题转化为求解关键路径问题–根据AOE网求解关键路径
关键路径所需的一些描述量
描述量的求解方法
最早发生时间求解例子 – 正在算
解析：尽管v1只需2天的时间就到了Vu活到开始，再过1天时间就可以结束。但是v1到Vx要长达82天的时间，而之后还有进行6天才能结束，所以要提前82+6天才能确保活到完成，这个时间也就是最早发生时间。
最晚发生时间求解例子 – 逆着算
示例
如图所示：
时间余量为0的活动就是关键活动，由关键活动组成的路径就是关键路径。
总结
