常用算法模板——搜索与图论：邻接矩阵与邻接表、DFS、BFS、拓扑排序、最短路径、最小生成树、二分图
C++算法模板系列
目录
0 搜索技巧
DFS
- 分析问题：画图、归纳
- 保存现场
- 剪枝
- 偏移量：适用于各种DFS、BFS等矩阵遍历情形。控制点在二维平面上移动的方向（搜索方向），可设定方向下标按顺时针（==上==、==右==、==下==、==左==）递增。此时对于方向下标
i，其反方向下标为i ^ 2（对2做按位异或运算），也可手动if设置求得。// 上(-1, 0)，右(0, 1)，下(1, 0)，左(0, -1) int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
BFS
- 必要时开距离数组记录第一次到达每个点时的距离（即为到达每个点的最短路距离）
- 求多源最短路时，可以设立一个超级源点（指向各源点的出边权值为0），则将问题转化为从超级源点到终点的单源最短路径。实际用BFS求时只需在初始化时将所有源点一次性入队即可。
1 树与图的存储
一般的树均可用图的方式来存储，无向图相当于弧均双向的特殊的有向图。
二叉树可用二叉链表存储。
1.1 邻接矩阵
注意无法存储重边，因此通常选择存储所有重边权中的最值。适合存稠密图，可随机存取任意边。
int g[N][N]; // g[a][b]存储有向边<a, b>
/* 初始化 */
memset(g, 0x3f, sizeof g);1.2 邻接表
相当于同时开 $n$ 条无头单链表，表h[k]存储点 $k$ 的所有出边。适合存稀疏图，可快速遍历某点的所有出边。
const int N = 1e5, M = 2 * N;
int n, m; // 点数、边数
int h[N], e[M], ne[M], idx; // h[k]为点k的边表的头指针
/* 初始化 */
memset(h, -1, sizeof h);
idx = 0;
/* 添加一条边<a, b> */
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}2 树与图的遍历
时间复杂度：$O(n+m)$
2.1 深度优先遍历(DFS)
bool st[N];
int dfs(int u) {
st[u] = true;
for (int i = h[u]; ~i; i = ne[i]) { // 遍历u的所有出边
int v = e[i];
if (!st[v]) {
dfs(v);
}
}
}2.2 宽度优先遍历(BFS)
bool st[N]; // V: [1 ... n]
void bfs() {
queue<int> q;
q.push(1); // 队中压入源点
st[1] = true;
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i]) { // 遍历点t的所有出边
int u = e[i];
if (!st[u]) {
st[u] = true;
q.push(u);
}
}
}
}3 拓扑排序
时间复杂度：$O(n+m)$
int n; // V: [1 ... n]
int q[N], hh = 0, tt = -1; // 顶点队列，存储拓扑序列
int d[N]; // d[i]存储点i的入度
/* 拓扑排序：将拓扑序列存在队列中 */
bool topsort() {
for (int i = 1; i <= n; i++) { // 将所有度为0的点入队
if (d[i] == 0) {
q[++tt] = i;
}
}
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) { // 遍历点t的所有出边
int u = e[i]; // 该出边对应的点u
if (--d[u] == 0) {
q[++tt] = u; // 删去该出边并判定：u入度变为0了则入队
}
}
}
return tt = n - 1; // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列
}
/* 输出拓扑序列（若存在） */
if (topsort()) {
for (int i = 0; i < n; i++) {
printf("%d ", q[i]);
}
puts("");
}4 最短路径
4.1 朴素Dijkstra算法
时间复杂度：$O(n^2+m)$
适用情形：稠密图
int n; // V: [1 ... n]
int g[N][N]; // 邻接矩阵图（带权）
int dist[N]; // dist[]存储起点到每个点的最短路径
bool st[N]; // st[]标记每个点的最短路是否已被确定
/* 求起点S到终点T的最短路，若不存在则返回-1 */
int dijkstra(int S, int T) {
memset(dist, 0x3f, sizeof dist);
dist[S] = 0; // 这里只先设起点的dist
for (int i = 0; i < n; i++) { // 迭代n次（第1轮预处理起点）
int t = -1; // 在还未确定最短路的点中，寻找最短距离点t
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
}
st[t] = true;
for (int j = 1; j <= n; j++) { // 用t更新其他点的距离
if (dist[j] > dist[t] + g[t][j]) {
dist[j] = dist[t] + g[t][j];
}
}
}
if (dist[T] == 0x3f3f3f3f) return -1;
return dist[T];
}4.2 堆优化Dijkstra算法
时间复杂度：$O(m\log n)$
适用情形：稀疏图
typedef pair<int, int> PII;
int n; // V: [1 ... n]
int h[N], e[M], w[M], ne[M], idx; // 邻接表图，w[i]存边i的权值
int dist[N]; // dist[]存储起点到每个点的最短路径
bool st[N]; // st[]标记每个点的最短路是否已被确定
/* 求起点S到终点T的最短路，若不存在则返回-1 */
int dijkstra(int S, int T) {
memset(dist, 0x3f, sizeof dist);
dist[S] = 0; // 这里也只先设起点的dist
priority_queue<PII, vector<PII>, greater<PII> > heap; // 小根堆
heap.push({0, S}); // (distance, vertex)
while (!heap.empty()) {
auto t = heap.top();
heap.pop();
int u = t.second, distance = t.first; // 用堆得到最近的点及与其距离
if (st[u]) continue; // 若已确定则跳过
st[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (dist[v] > distance + w[i]) {
dist[v] = distance + w[i];
heap.push({dist[v], v});
}
}
}
if (dist[T] == 0x3f3f3f3f) return -1;
return dist[T];
}4.3 Bellman-Ford算法
时间复杂度：$O(nm)$
适用情形：存在负权边的图
int n, m; // V: [1 ... n]
struct Edge {
int a, b, w;
} edges[M]; // 边集，存储权值为w的有向边<a, b>
int dist[N]; // dist[]存储起点到每个点的最短路径
/* 求起点S到终点T的最短路，若不存在则返回-1 */
int bellman_ford(int S, int T) {
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
for (int i = 0; i < n; i++) { // 要求最大长度为n的最短路径，故迭代n次
for (int j = 0; j < m; j++) { // 每次遍历全部m条边
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w) { // 松弛操作：更新当前dist
dist[b] = dist[a] + w;
}
}
}
if (dist[T] > 0x3f3f3f3f / 2) return 0x3f3f3f3f; // 因为负权边的存在，可能略低于INF
return dist[T];
}应用：求有边数限制的最短路
限制 $k$ 条边就进行 $k$ 轮迭代遍历，遍历开始前需先备份 dist[]于 backup[]，用其将 dist[]更新。
int n, m, k; // 限制最短路最多经过k条边
struct Edge {
int a, b, w;
} edges[M];
int dist[N], backup[N]; // backup[]备份dist[]数组，防止发生串联（用改后数据去改别人）
/* 求起点S到终点T的最短路，若不存在则返回-1 */
int bellman_ford(int S, int T) {
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
for (int i = 0; i < k; i++) { // 限制k条边，则迭代k次
memcpy(backup, dist, sizeof dist); // 遍历边前先将dist拷贝至备份数组
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > backup[a] + w) { // 使用备份数组做松弛操作
dist[b] = backup[a] + w;
}
}
}
if (dist[T] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
return dist[T];
}4.4 SPFA算法
时间复杂度：平均 $O(m)$ ，最坏 $O(nm)$
队列优化的Bellman-Ford算法，后继变小了当前dist才变小。
int n; // V: [1 ... n]
int h[N], e[M], w[M], ne[M], idx; // 邻接表图，w[i]存边i的权值
int dist[N]; // dist[]存储起点到每个点的最短路径
bool st[N]; // st[]标记每个点的最短路是否已被确定
int spfa(int S, int T) {
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
queue<int> q; // 队中存放待更新的点（用堆也行）
q.push(S);
st[S] = true; // 结点入队时做标记
while (!q.empty()) { // 使用BFS的思想
auto t = q.front();
q.pop();
st[t] = false; // 结点出队时撤销标记（之后可能需再次入队被更新）
for (int i = h[t]; ~i; i = ne[i]) {
int u = e[i];
if (dist[u] > dist[t] + w[i]) {
dist[u] = dist[t] + w[i];
if (!st[u]) { // 若更新了u的距离，则其出边所指也可能待更新，判断将其入队
q.push(u);
st[u] = true;
}
}
}
}
if (dist[T] == 0x3f3f3f3f) return 0x3f3f3f3f;
return dist[T];
}应用：判断图中是否存在负环
时间复杂度：$O(nm)$
不需要初始化 dist[]，因此之后正权入边顶点永不会被更新。并且为了消除某点可能无法到达负环的影响，将所有点全入队并标记！
原理：若某条最短路径上有 $n$ 个点（除了自己），则加上自己之后一共有 $n+1$ 个点，由抽屉原理一定有两个点相同，所以存在负环。
int n;
int h[N], e[M], w[M], ne[M], idx;]
int dist[N], cnt[N]; // cnt[x]存储起点（任意）到x的最短路中经过的点数
bool st[N];
/* 如果存在负环，则返回true，否则返回false */
bool spfa() {
queue<int> q; // 不需要初始化dist数组，直接将所有点全入队并标记！
for (int i = 1; i <= n; i++) {
q.push(i);
st[i] = true;
}
while (!q.empty()) {
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i]) {
int u = e[i];
if (dist[u] > dist[t] + w[i]) {
dist[u] = dist[t] + w[i];
cnt[u] = cnt[t] + 1; // 若更新了u的距离，则立即更新其cnt（前驱加1）
if (cnt[u] >= n) return true; // 若最短路已包含至少n个点（不含自身），则有负环
if (!st[u]) {
q.push(u);
st[u] = true;
}
}
}
}
return false; // 跳出循环则说明无负环
}4.5 Floyd算法
时间复杂度：$O(n^3)$
基于动态规划
int n, m; // V: [1 ... n]
int dist[N][N]; // 邻接矩阵图，经过Floyd()操作后变为存储最短距离
/* 初始化 */
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = 0x3f3f3f3f; // 之后被更新为边权
}
}
}
/* 算法结束后，d[a][b]表示a到b的最短距离 */
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}5 最小生成树
5.1 朴素版Prim算法
时间复杂度：$O(n^2+m)$
必须先累加 res再更新 dist[]，以避免负自环污染当前 t最短距离
const int INF = 0x3f3f3f3f;
int n; // V: [1 ... n]
int g[N][N]; // 邻接矩阵图
int dist[N]; // dist[]存储起点到当前最小生成树(MST)的最短距离
bool st[N]; // st[]标记每个点是否已经在生成树中
/* 若图不连通，则返回INF，否则返回最小生成树的最小代价 */
int prim() {
memset(dist, 0x3f, sizeof dist); // 仅计算最小代价，故无需另设起点，不应先置标记为true
int res = 0; // 存储最小代价
for (int i = 0; i < n; i++) { // 迭代n次（第1轮预处理生成树根）
int t = -1; // 在还未并入MST的点中，寻找最短距离点t
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
}
if (i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f; // 从第2轮起，若最短距离为无穷，则说明不连通
if (i) {
res += dist[t]; // 从第2轮起，将t的距离计入最小代价（须先累加res）
}
st[t] = true; // 将t并入MST
for (int j = 1; j <= n; j++) { // 用新并入的t更新各点到生成树的距离
if (dist[j] > g[t][j]) { // 与dij不同，不应加前驱的dist（求取到整棵树的距离）
dist[j] = g[t][j];
}
}
}
return res;
}5.2 Kruskal算法
时间复杂度：$O(m\log m)$
int n, m; // V: [1 ... n]
struct Edge {
int a, b, w;
bool operator<(const Edge &t) const { // 重载运算符，用于按权递增排序
return w < t.w;
}
} edges[MAXM]; // 边集，存储权值为w的有向边<a, b>
int p[N]; // 并查集
/* 并查集核心操作 */
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
/* 若图不连通，则返回INF，否则返回最小生成树的最小代价 */
int kruskal() {
sort(edges, edges + m); // 将边按权递增排序（方式不限）
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) { // 枚举所有边，将合适的边并入MST（加入集合）
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
if (find(a) != find(b)) { // 如果两个连通块不连通，则将这两个连通块合并
p[find(a)] = find(b);
res += w;
cnt++;
}
}
if (cnt < n - 1) return 0x3f3f3f3f; // 判定连通性（连通的必要条件：|E| = |V| - 1）
return res;
}6 二分图
定义：二分图可将图中顶点划分两个集合，使得集合内顶点互不邻接，不同集合顶点可邻接
定理：图为二分图 $\Leftrightarrow$ 图中不含奇数环
6.1 染色法
时间复杂度：$O(n+m)$
判断是否是二分图
思想：若为二分图，则与黑点相连的点均为白色，与白点相连的点均为黑色（邻接顶点不得同色）
int n; // V: [1 ... n]
int h[N], e[M], ne[M], idx; // 邻接表图
int color[N]; // 每个点的颜色：-1未染色，0白色，1黑色
/* 用dfs给结点u染颜色c，一切顺利返回true，出现冲突则返回false */
bool dfs(int u, int c) {
color[u] = c; // 给结点u染颜色c
for (int i = h[u]; ~i; i = ne[i]) { // 遍历所有从结点u指出的点
int v = e[i];
if (color[v] == -1) { // 若v未染色则将其染与u相反的色(!c)并判定是否冲突
if (!dfs(v, !c)) return false;
} else if (color[v] == c) {
return false; // 若v与u同色则出现冲突
}
}
return true;
}
/* 用染色法判断图是否是二分图 */
memset(color, -1, sizeof color);
bool success = true;
for (int i = 1; i <= n; i++) { // 遍历所有顶点，若未染色则染白色并判定是否冲突
if (color[i] == -1) {
if (!dfs(i, 0)) {
success = false;
break;
}
}
}6.2 匈牙利算法
时间复杂度：最差 $O(nm)$ ，实际运行时间一般远小于 $O(nm)$
用于求二分图的最大匹配数（匹配：某两个点有且只有他们之间有边，与别人无边）
匈牙利算法中只会用到从第1个集合指向第2个集合的边，所以这里只用存一个方向的边。
int n1, n2; // 二分图中两个集合的点数。集合1: [1 ... n1]、集合2: [1 ... n2]
int h[N], e[M], ne[M], idx; // 邻接表图，只存集合1到集合2的边
int match[N]; // match[i] = j表示集合2的点i当前匹配集合1的点j（j=0表示暂无匹配）
bool st[N]; // st[i]标记集合2的点i是否已经被遍历过
/* 寻找与集合1的点u匹配集合2的点，返回是否成功 */
bool find(int u) {
for (int i = h[u]; ~i; i = ne[i]) { // "遍历所有可能"
int v = e[i];
if (!st[v]) {
st[v] = true;
if (match[v] == 0 || find(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}
/* 求最大匹配数 */
int res = 0;
for (int i = 1; i <= n1; i++) { // 依次枚举集合1的每个点去匹配集合2的点
memset(st, false, sizeof st); // 每次重置遍历标记
if (find(i)) {
res++;
}
}
《C++算法模板（3）：搜索与图论》有3条评论