图的应用 | Lzc's blog

最小生成树（MST）

权值之和最小的生成树称为最小生成树（Minimum-Spanning-Tree, MST）

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树而言，若减一条边，则使生成树变成非连通图；若加一条边，则会形成图的一条回路。
生成树不同，每棵树的权值之和也可能不同。

MST的性质

若图 $G$ 中存在权值相同的边，则 $G$ 的最小生成树可能不唯一，即最小生成树的树形不唯一。当图 $G$ 中的各边权值互不相等时， $G$ 的最小生成树是唯一的；若无向连通图 $G$ 的边数等于顶点数-1，即 $G$ 本身是一棵树时，则MST为本身。
MST树形不唯一，但权值之和总唯一，且最小。
MST的边数 = 顶点数 - 1

假设 $G=(V,E)$ 是一个带权连通无向图， $U$ 是顶点集 $V$ 的一个非空子集。若 $(u,v)$ 是一条具有最小权值的边，其中 $u\in U,v\in V-U$ ，则必存在一棵包含 $(u,v)$ 的最小生成树。

找到一条权值最小边 $(u,v)$ 并且加入 $T$ 后不会产生回路，显然这是贪心思想。

Prim算法和Kruskal算法都是基于贪心算法的。

Prim

Prim算法的时间复杂度为 $O(|V|^2)$ ，不依赖于边数，因此它适合边稠密的图。

初始时从图中任取一顶点加入树T，此时树中只含一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增加1。如此反复，直至所有顶点都加入T。

步骤如下：

假设 $G=(V,E)$ 是连通图，其最小生成树 $T=(U,E_T)$ ， $E_T$ 是MST中边的集合。
初始化：向空树 $T=(U,E_T)$ 中添加图 $G=(V,E)$ 中的任意一个顶点 $u_0$ ，使 $U=\{u_0 \}, E_T = ∅$ 。
循环（重复直至 $U=V$ ）：从图 $G$ 中选择满足 $\{(u,v)|u\in U,v\in V-U \}$ 且具有最小权值的边 $(u,v)$ ，加入树 $T$ ，置 $U=U ∪ \{v \},E_T=E_T ∪\{(u,v) \}$ 。

Kruskal

Kruskal算法的时间复杂度为 $O(|E|\log_2|E|)$ ，不依赖于顶点数，因此它适合边稀疏而顶点较多的图

初始时为只有n个顶点而无边的非连通图 $T=\{V,\{\} \}$ ，每个顶点自成一个连通分量。然后按照边的权值由小到大的顺序，不断的选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量（使用并查集判断这两个顶点是否同属一棵树），若不在则将此边加入T，否则舍弃。如此反复，直至T中所有顶点都在一个连通分量上。

步骤如下：

假设 $G=(V,E)$ 是连通图，其最小生成树 $T=(U,E_T)$ 。
初始化： $U=V,E_T= ∅$ 。即每个顶点构成一棵独立的树， $T$ 此时是一个仅含 $|V|$ 个顶点的森林。
循环（重复直至 $T$ 是一棵树）：按 $G$ 的边的权值递增顺序依次从 $E-E_T$ 中选择一条边，若此边加入后不构成回路，则加入，否则舍去，直至 $E_T$ 中含有 $n-1$ 条边。

最短路径

当图是带权图时，把从一个顶点 $v_0$ 到图中其余任意一个顶点 $v_i$ 的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径（可能不止一条）成为最短路径。

最短路径的性质：两点之间的最短路径也包含了路径上其他顶点间的最短路径。

带权有向图的最短路径问题一般可分为两类：

单源最短路径：求图中某一顶点到其他各个顶点的最短路径。Dijkstra、Bellman-Ford
多源最短路径：求图中任意两个顶点之间的最短路径。Floyd

Dijkstra

时间复杂度 $O(|V|^2)$ ，边权非负。贪心策略。

初始时，把源点 $v_0$ 放入 $S$ ，集合 $S$ 每并入一个新顶点 $v_i$ ，都要修改源点 $v_0$ 到集合 $V-S$ 中顶点当前的最短路径长度值。

以A为源点的Dijkstra求解过程：

顶点	第1轮	第2轮	第3轮	第4轮
B	3 A-B
C	20 A-C	18 A-B-C
D	∞	∞	40 A-C-D
E	45 A-E	43 A-B-E	43 A-B-E	43 A-B-E
集合S	{A,B}	{A,B,C}	{A,B,C,D}	{A,B,C,D,E}

【图-最短路径-Dijkstra(迪杰斯特拉)算法】

Bellman-Ford

时间复杂度 $O(|V||E|)$ ，边权可负。

Floyd

插点法。时间复杂度 $O(|V|^3)$ ，边权可负。

Floyd利用DP的思想寻找给定的加权图中多源点之间最短路径的算法。

拓扑排序

有向无环图：若一个有向图不存在环，则成为有向无环图，简称DAG图（Directed Acyclic Graph）。

AOV 网 (Activity On Vertex Network)：若用DAG图表示一个工程，其顶点表示活动，用有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系，则将这种有向图成为顶点表示活动的网络，简称AOV网。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

每个顶点出现且只出现一次
若顶点A的序列中排在顶点B的前面，则在图中不存在从B到A的路径。

或定义为：拓扑排序时对DAG图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中B出现在A的后面。

每个AOV网都有一个或多个拓扑排序。

关键路径

最耗时的路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为边表示活动的网络，简称 AOE 网（Activity On Edge Network) 。
AOE网和AOV网都是DAG图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中所有的边有权值；而AOV网中的边无权值，仅表示顶点之间的前后关系。