DSA之图（4）：图的应用

0 图的应用

1 生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图。
也就是两个条件，顶点条件和边数条件，顶点都要保持连通，边数达到最少，没有回路。

如右边的图，随便再加一条边就有回路了。
所有生成树都具有以下的共同特点：

• 生成树的顶点个数与图的顶点个数相同；
• 生成树是图的极小连通子图，去掉一条边则非连通；
• 一个有$n$个顶点的连通图的生成树有$n-1$条边；
• 生成树中任意两个顶点间的路径是唯一的；
• 含有$n$个顶点$n-1$条边的图不一定是生成树，如下图所示
  
  因为生成树是连通的，每个顶点都要用边相连，上图是不连通的，有两个连通分量。

1.1 无向图的生成树

生成树要包含所有顶点，那么对图进行遍历，把走过的边全部加入到图当中。
遍历则采用DFS与BFS都可以。

用DFS生成的生成树就是DFS生成树。

用BFS生成的生成树就是BFS生成树。

综上

1.2 最小生成树

最小生成树：给定一无向网络在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。
最小生成树可能是不唯一的。

1.2.1 构造最小生成树

构造最小生成树的算法很多，其中多数算法都利用了MST(Minimum Spanning Tree)的性质。

MST性质：
其实就是贪心算法，不断去找权值最小的边。
设$N=(V,E)$以目是一个连通网，$U$是顶点集$V$的一个非空子集。若边$(u,v)$是一条具有最小权值的边，其中$u\in U,v\in V-U$则必存在一棵包含边$(u,v)$的最小生成树。

举例

现在 U = { v 1 } U=\{v_1\} U={v1​}，所以 V − U = { v 2 , v 3 , v 4 , v 5 , v 6 } V-U=\{v_2,v_3,v_4,v_5,v_6\} V−U={v2​,v3​,v4​,v5​,v6​}，所以$u\in U,v\in V-U$当中，其中从$v_1$到$v_3$是最小的，权值为1，存在这个权值最小的边，这条边一定会包含在某个最下生成树当中。

1.2.2 Prim算法构造最小生成树

算法思想：

1.2.3 Kruskal算法构造最小生成树

相比Prim算法更加贪心，直截了当贪心，前提不成环。这次开始就把所有顶点都加入到最小生成树上面去。不过并不包括边，这时边的集合都是空集，没包含边，彼此之间不连通。

然后直接在边集合当中选权值最小的边，直接加入。
以此类推，选到所有顶点都连通为止（前提不能形成回路）（n个点，n-1条边）。

1.2.4 两种算法的比较

Prim是选择点加入的，而Kruskal是选择边的。选择边的时候和顶点数是没关系的。

1.3 最短路径

1.3.1 两点间最短路径

从起点走向终点，并非要n个节点都包括，也并非要n-1条边。
直到找到路径长度最短的一条路径。
这种最短路径也称为单源的最短路径，采用Dijkstra算法。

1.3.2 某源点到其他各点最短路径

所有顶点的最短路径，统一使用Floyd弗洛伊德算法。

1.3.3 Dijkstra

其时间复杂度为$O(n^3)$

按照路径长度递增次序产生最短路径，启发式贪心算法。


启发式算法，先找最短的，后面再及时更新，具体过程可以看王老师的视频。

1.3.4 Floyd

其时间复杂度为$O(n^3)$

算法思想：

• 逐个顶点试探
• 从少，到的所有可能存在的路径中
• 选出一条长度最短的路径

求最短路径的步骤：
初始时设置一个$n$阶方阵，令其对角线元素（到自身的路径）为0，若存在弧$<v_i,v_j>$，则对应元素为权值；否则为$\infty$。
逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束。

1.4 拓扑排序

1.4.1 有向无环图DAG

AOV网以顶点表示活动；AOE网用弧表示活动（子工程）。
AOV网用来解决拓扑排序，AOE网用来解决关键路径问题。

拓扑排序的一个小例子：

1.4.2 AOV网

问题：如何判断AOV网中是否存在回路？
答：

所有顶点都能加入拓扑排序的话，就一定没有网。

拓扑排序。
将网变成一个线性序列的过程就是拓扑排序。

拓扑排序的步骤：

1. 首先构建好AOV网

2. 在有向图中选一个没有前驱的顶点且输出（例如C1和C9）
3. 假设选了C1，在有向图当中删除该顶点和所有以它为尾的弧（C1发出的弧）（即C1与C2，C4，C12的弧）
4. 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

1.5 关键路径

制定计划，查找关键路径。
关键路径就是从源点到汇点路径长度（权值之和）最长（大）的路径。

按照任务需求，构建有权图。

举例：

对于上方AOE网，我们关心两个问题：

1. 完成整项女程至少需要多少时间？
2. 哪些活动是影响工程进度的关键？

以上答为关键路径与路径长度。

1.5.1 求解关键路径

四个有用的量：



求关键路径的步骤：