图论

最小生成树

最小生成树 (Minimum Spanning Tree, MST) 即对于一个给定的图结构，选择全部的点和部分的边，使得可以组成一棵树且该树的总权重最小，对应的树就是最小生成树。该算法在很多场景都有实际的应用价值，例如最小化城市之间的道路铺设等。

Prim 算法。这是一种贪心算法。具体地，假设图中包含 \(n\) 个顶点，初始时顶点集合 \(U\) 含 \(1\) 个顶点，顶点集合 \(V-U\) 含 \(n-1\) 个顶点。我们需要构造 \(n-1\) 个「割」的状态并维护两个顶点集合之间的交叉边信息。对于每一个状态，我们将「最小交叉边在集合 \(V-U\) 中的顶点」加入到集合 \(U\) 中并更新交叉边信息。这样得到的顶点集 \(U\) 及其边集就是最终的最小生成树。时间复杂度 \(O(n^2)\)。

Kruskal 算法。这也是一种贪心算法，并使用了并查集数据结构加速了一些集合操作。具体地，我们初始化 \(n\) 个顶点作为 \(n\) 个连通分量，接着将所有的边按照权值升序排序，然后枚举所有的边，如果当前边的两个顶点不在同一个集合，则加入最小生成树，如果当前边的两个顶点在同一个集合，则不选择（如果选了就会使得生成树形成回路）。时间复杂度 \(O(e\log e)\)。

最短路

最短路 (Shortest Path) 顾名思义就是求解图中顶点之间的最短路径。分为单源最短路和多源最短路两种策略。所有的最短路算法都是基于动态规划进行的。

Dijkstra 算法。单源最短路算法（无法求解含负边权的单源最短路）。分为朴素版和堆优化版。具体地：

朴素版。采用邻接矩阵存储图。时间复杂度 \(O(n^2)\)。算法流程如下：
- 定义 \(d[i]\) 表示从起点到当前 \(i\) 号点的最短路径的长度；
- 将顶点分为 \(U\) 和 \(V-U\) 两个集合，其中 \(U\) 表示已经更新了最短路径长度的顶点集合；
- 枚举集合 \(V-U\) 中的结点 \(v_i\in V-U\)，选择 \(U\) 中到当前结点 \(v_i\) 最近的顶点 \(v_j\) 并更新 d[i] = d[j] + edges[j][i]。
堆优化版。采用邻接表存储图。时间复杂度 \(O(e \log e)\)。

Bellman-Ford 算法。单源最短路算法（支持负边权）。

Spfa 算法。单源最短路算法（同样支持负边权的单元最短路，属于 Bellman-Ford 算法的优化版）。

Floyd 算法。多源最短路算法（支持负边权）。多阶段决策共 \(n\) 个阶段，dp[i][j] 表示每一个阶段 \(k\)，从 \(i\) 到 \(j\) 的选择前 \(k\) 个顶点后的最短路径的长度。对于当前阶段 \(k\)，我们利用阶段 \(k-1\) 的状态进行转移更新，其实就是对于新增加的顶点 \(v_k\) 是否选择的过程：

选择 \(v_k\)，则 dp[i][j] = dp[i][k] + dp[k][j]；
不选 \(v_k\)，则 dp[i][j] 就是 \(k-1\) 状态下的 dp[i][j]。

拓扑排序

首先介绍一下用顶点表示活动的网 (activity on vertex network, AOV 网)。顾名思义，在这种图中，顶点就是活动，边就是时间上的约束关系，边的起点活动在时间上必须要优先于边的终点活动。这种网一般用来描述在时间上有先后约束的工程管理问题。

而为了判定一个图是否满足 AOV 的结构，拓扑排序应运而生。当然 AOV 的结构由于不具备后效性，也可以确保在其之上进行动态规划的理论正确性。拓扑排序的一般思路是：从所有的入度为 \(0\) 的点开始缩点删边，最后的图中如果所有的点和边都被删除了，就说明这个图是可拓扑的，反之就是不可拓扑的。可以采用深度优先，也可以采用广度优先。时间复杂度为 \(O(n+e)\)。