文章目录
- 0 图的应用
- 1 生成树
- 1.1 无向图的生成树
- 1.2 最小生成树
- 1.2.1 构造最小生成树
- 1.2.2 Prim算法构造最小生成树
- 1.2.3 Kruskal算法构造最小生成树
- 1.2.4 两种算法的比较
- 1.3 最短路径
- 1.3.1 两点间最短路径
- 1.3.2 某源点到其他各点最短路径
- 1.3.3 Dijkstra
- 1.3.4 Floyd
- 1.4 拓扑排序
- 1.4.1 有向无环图DAG
- 1.4.2 AOV网
- 1.5 关键路径
- 1.5.1 求解关键路径
0 图的应用
1 生成树
生成树：所有顶点均由边连接在一起，但不存在回路的图。
也就是两个条件，顶点条件和边数条件，顶点都要保持连通，边数达到最少，没有回路。
如右边的图，随便再加一条边就有回路了。
所有生成树都具有以下的共同特点：
- 生成树的顶点个数与图的顶点个数相同；
- 生成树是图的极小连通子图，去掉一条边则非连通；
- 一个有 n n n个顶点的连通图的生成树有 n − 1 n-1 n−1条边；
- 生成树中任意两个顶点间的路径是唯一的；
- 含有
n
n
n个顶点
n
−
1
n-1
n−1条边的图不一定是生成树，如下图所示
因为生成树是连通的，每个顶点都要用边相连，上图是不连通的，有两个连通分量。
1.1 无向图的生成树
生成树要包含所有顶点，那么对图进行遍历，把走过的边全部加入到图当中。
遍历则采用DFS与BFS都可以。
用DFS生成的生成树就是DFS生成树。
用BFS生成的生成树就是BFS生成树。
综上
1.2 最小生成树
最小生成树：给定一无向网络在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。
最小生成树可能是不唯一的。
1.2.1 构造最小生成树
构造最小生成树的算法很多，其中多数算法都利用了MST(Minimum Spanning Tree)的性质。
MST性质：
其实就是贪心算法，不断去找权值最小的边。
设
N
=
(
V
,
E
)
N=(V, E)
N=(V,E)以目是一个连通网，
U
U
U是顶点集
V
V
V的一个非空子集。若边
(
u
,
v
)
(u, v)
(u,v)是一条具有最小权值的边，其中
u
∈
U
,
v
∈
V
−
U
u∈U,v∈V-U
u∈U,v∈V−U则必存在一棵包含边
(
u
,
v
)
(u,v)
(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
∈
U
,
v
∈
V
−
U
u∈U,v∈V-U
u∈U,v∈V−U当中，其中从
v
1
v_1
v1到
v
3
v_3
v3是最小的，权值为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
)
O(n^3)
O(n3)
按照路径长度递增次序产生最短路径，启发式贪心算法。
启发式算法，先找最短的，后面再及时更新，具体过程可以看王老师的视频。
1.3.4 Floyd
其时间复杂度为 O ( n 3 ) O(n^3) O(n3)
算法思想：
- 逐个顶点试探
- 从少，到的所有可能存在的路径中
- 选出一条长度最短的路径
求最短路径的步骤：
初始时设置一个
n
n
n阶方阵，令其对角线元素（到自身的路径）为0，若存在弧
<
v
i
,
v
j
>
<v_i, v_j>
<vi,vj>，则对应元素为权值；否则为
∞
∞
∞。
逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束。
1.4 拓扑排序
1.4.1 有向无环图DAG
AOV网以顶点表示活动；AOE网用弧表示活动（子工程）。
AOV网用来解决拓扑排序，AOE网用来解决关键路径问题。
拓扑排序的一个小例子：
1.4.2 AOV网
问题：如何判断AOV网中是否存在回路？
答：
所有顶点都能加入拓扑排序的话，就一定没有网。
拓扑排序。
将网变成一个线性序列的过程就是拓扑排序。
拓扑排序的步骤：
- 首先构建好AOV网
- 在有向图中选一个没有前驱的顶点且输出（例如C1和C9）
- 假设选了C1，在有向图当中删除该顶点和所有以它为尾的弧（C1发出的弧）（即C1与C2，C4，C12的弧）
- 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
1.5 关键路径
制定计划，查找关键路径。
关键路径就是从源点到汇点路径长度（权值之和）最长（大）的路径。
按照任务需求，构建有权图。
举例：
对于上方AOE网，我们关心两个问题：
- 完成整项女程至少需要多少时间？
- 哪些活动是影响工程进度的关键？
以上答为关键路径与路径长度。
1.5.1 求解关键路径
四个有用的量：
求关键路径的步骤：
