Acwing《算法基础课》第3章 搜索与图论

文章目录

Acwing《算法基础课》第3章 搜索与图论深度优先遍历DFS宽度优先搜索BFS拓扑排序dijkstra算法朴素dijkstra算法堆优化dijkstra算法 Bellman-Ford朴素Bellman-Ford算法队列优化Bellman-Ford算法——SPFA算法 Floyd算法Prim算法Kruskal算法染色法匈牙利算法

---

深度优先遍历DFS

模板：

bool st[N]; // 标记是否用过 int h[N], ne[N]; int dfs(int u) { if (...) {...; return;} // 输出结果，记得加return语句（或者后边部分用else括起） st[u] = true; // st[u] 表示点u已经被遍历过 for (int p = h[u]; p != -1; p = ne[p]) { int v = e[p]; if (!st[v]) dfs(v); } st[u] = false; // 恢复现场 }

说明：

空间复杂度为$O(h)$，对空间复杂度高的考虑DFS不具备最短性

宽度优先搜索BFS

模板：

queue<int> q; st[1] = true; // 表示1号点已经被遍历过 q.push(1); while (q.size()) { int u = q.front(); q.pop(); for (int p = h[u]; p != -1; p = ne[p]) { int v = e[p]; if (!st[v]) { st[v] = true; // 表示点j已经被遍历过 q.push(v); } } }

说明：

如果手动实现queue，则容量一般取N * NBFS只适用边权为1的迷宫

拓扑排序

模板：

int d[N]; // 入度 bool topsort() { int hh = 0, tt = -1; // d[i] 存储点i的入度 for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (-- d[j] == 0) q[ ++ tt] = j; } } // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。 return tt == n - 1; }

说明：

有向无环图又称拓扑图有向无环图一定至少存在一个入度为0的点（反证法 + 抽屉原理证明）当循环结束后，若队列的长度为n，则拓扑排序存在在添加边时，可以顺便统计入度可以使用其它数据结构存储结果（例如线性表，栈等，甚至是集合）时间复杂度是$O(n+m)$

dijkstra算法

朴素dijkstra算法

模板：

int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); // 0x3f3f3f3f作为距离的“最大值” dist[1] = 0; // 自己到自己的距离为0 for (int i = 0; i < n - 1; i ++ ) // 执行n-1次（自己到自己的距离已经确定） { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 用t更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); st[t] = true; } if (dist[n] == 0x3f3f3f3f) return -1; // 不可达 return dist[n]; }

说明：

由于最多有$10^5$条边，且每条边的长度不超过$10^4$，因此最大距离不超过$10^9$，0x3F3F3F3F比$10^9$大一些，因此可当做距离的最大值。好处是只用一行memset(d, 0x3f, sizeof d)就能实现把d数组各值初始化为“最大值”t == -1 || dist[t] > dist[j]使得t不必选第1个标记，实际上t = 1也是可以的，只需把循环条件从j = 2开始就可以min(dist[j], dist[t] + g[t][j])不要错写成min(dist[j], g[1][t] + g[t][j])对于重边的条件，不能使用编译器赋予的初值0，而应该赋予一个比边长最大值更大的值，例如memset(g, 0x3f, sizeof g)，然后用g[a][b] = min(g[a][b], c)记录最小的重边即可时间复杂度为$O(n^2+m)$

堆优化dijkstra算法

模板：

typedef pair<int, int> PII; int n; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 // 求1号点到n号点的最短距离，如果不存在，则返回-1 int dijkstra() { memset(dist, 0x7f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆 heap.push({0, 1}); // first存储距离（顶点1到顶点second的距离），second存储尾顶点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x7f7f7f7f) return -1; return dist[n]; }

说明：

边长最大值为$10^4$，最多有$1.5\times 10^5$条边，因此距离最大值为$1.5\times 10^9$，因此0x3f3f3f3f不可代表最大值，可用0x7f7f7f7f代替改用邻接表数据结构使用小根堆优化查找最小距离的过程小根堆可能存在冗余数据算法类似BFS，因为在修改其它顶点最短距离的过程中，堆优化版本并没有遍历所有的顶点，而是遍历所有与当前选取的最小顶点有关的边时间复杂度为$O(m\text{log}n)$

Bellman-Ford

朴素Bellman-Ford算法

模板：

int n, m, k; // n表示点数，m表示边数，k是路径的最大边数 int dist[N], backup[N]; // dist[x]存储1到x的最短路距离 // 三元组 struct Edge // 边，a表示出点，b表示入点，w表示边的权重 { int a, b, w; }edges[M]; // 求1到n的最短路距离，如果无法从1走到n，则返回-1。 int bellman_ford() { memset(dist, 0x7f, sizeof dist); dist[1] = 0; // 如果第n次迭代仍然会松弛三角不等式（存在更新），就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i < k; i ++ ) // 如果没有k，则用n代替k { memcpy(backup, dist, sizeof dist); // 备份，防止读后写 for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; dist[b] = min(dist[b], dist[a] + w) } } if (dist[n] > 0x7f7f7f7f / 2) return -1; return dist[n]; }

说明：

除了可以用邻接矩阵和邻接表外，还可用三元组存储图允许存在负权边，而Dijkstra算法不允许外循环次数决定最小路径的最大边数 若第n次迭代有修改，根据容斥原理知道，一定存在负权环（整个环的权重和为负数）实际应用：换乘不超过$k$次的最短路径（限制路径的边数） backup用于保存上次迭代的结果，避免“写后读”。Dijkstra算法不存在这种情况由于存在负权回路（注意不是负权边），因此负权回路有可能把自定义的无穷大0x7f7f7f7f变小，由于最多修改$10000\times 10000=10^8$，而0x7f7f7f7f$>2\times 10^8$，故0x7f7f7f7f / 2依旧是“无穷大”，故可用dist[n] > 0x7f7f7f7f / 2判断是否是无穷大时间复杂度为$O(mn)$

队列优化Bellman-Ford算法——SPFA算法

模板：

int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到1号点的最短距离 bool st[N]; // 存储每个点是否在队列中 // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1 int spfa() { memset(dist, 0x7f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; // 已出队，因此队列不再包含顶点t，需要重置为false for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } } if (dist[n] == 0x7f7f7f7f) return -1; // 如果题目保证不存在负权回路（不是指负权边），则可这么写 return dist[n]; }

说明：

用队列优化更新最短距离的过程，核心思想是 dist[u]发生改变，dist[u] + w才有可能满足< dist[u]用队列保存最短距离发生改变的顶点（其它数据结构也可以，不一定是队列）用st记录在队列中的顶点，避免重复更新由于每次只更新与出队顶点相关的边，因此不会出现“写后读”现象，故改进的bellman-ford算法不需要额外的数组保存上次迭代的结果 SPFA算法有点像堆优化的Dijkstra算法，但后者依赖优先队列，而前者不需要大多数情况下，Dijkstra算法能解决的问题，SPFA都比它更好，而且适用负权边，因此如果没有限制路径最大边数的情况下，优先考虑SPFA算法，如果过不了就考虑堆优化的Dijkstra算法平均时间复杂度为$O(m)$，最坏时间复杂度为$O(mn)$若要判断负环，则需要额外维护一个数组cnt，用于记录各个最短路径的边数，当边数≥顶点数n时，则一定存在负环

Floyd算法

模板：

const int INF = 1E9; // 初始化： for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // 算法结束后，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 ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }

说明：

最短距离需要把d[i][i] = 0;时间复杂度为$O(n^3)$

Prim算法

模板：

cosnt int INF = 0x3f3f3f3f; int n; // n表示点数 int g[N][N]; // 邻接矩阵，存储所有边 int dist[N]; // 存储其他点到当前最小生成树的距离(集合到点u的距离) bool st[N]; // 存储每个点是否已经在生成树中 // 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和 int prim() { memset(dist, 0x3f, sizeof dist); int res = 0; for (int i = 0; i < n; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; if (i && dist[t] == INF) return INF; // 非首次遍历时，出现集合到其它点都是无穷大的情况，则图为非连通图 if (i) res += dist[t]; // 第1次迭代得到的dist为无穷大，没意义 st[t] = true; for (int j = 1; j <= n; j ++ ) if(!st[j]) dist[j] = min(dist[j], g[t][j]); // 可不加if，集合内点的dist应失去意义（受自环影响） } return res; }

说明：

注意最小生成树解决的是无向图问题，因此存储边时要添加两条有向边允许存在负权边、自环、重边 对于自环，需要先保存最短路径长度，再更新集合到其它点的距离，避免负权自环更新自己，出现写后读问题对于重边，需要初始化各个点的距离为INF，然后用min读入边 应用场景：多城市发电站的选址问题可类似Dijkstra算法，用堆优化Prim算法，时间复杂度为$O(m\text{log}n)$，但由于这个算法只适用稀疏图（因为如果是稠密图的话，性能还不如朴素的Prim算法），对于稀疏图来说，$n$≈$m$，此时性能和kruskal算法接近$O(m\text{log}m)$，而kruskal算法代码更简洁，因此一般不用堆优化的Prim算法Prim算法和Dijkstra算法非常相似 Prim算法更新其他点到集合的距离Dijkstra算法更新其它点到起点的距离 采用邻接矩阵保存图，适用稠密图，时间复杂度为$O(n^2+m)$

Kruskal算法

模板：

int n, m; // n是点数，m是边数 int p[N]; // 并查集的父节点数组 // 三元组 struct Edge // 存储边 { int a, b, w; // 重载<，用于sort排序 bool operator< (const Edge &W)const { return w < W.w; } }edges[M]; int find(int x) // 并查集核心操作 { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int kruskal() { sort(edges, edges + m); // 快排，+m是地址运算，得到数组末尾 for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集 int res = 0, cnt = 0; // cnt统计边数 for (int i = 0; i < m; i ++ ) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a), b = find(b); if (a != b) // 如果两个连通块不连通，则将这两个连通块合并 { p[a] = b; res += w; cnt ++ ; } } if (cnt < n - 1) return INF; // 边数小于n-1，不连通 return res; }

说明：

用于求解稀疏图的最小生成树采用三元组存储图时，没必要保存两条有向边实际上是并查集的简单应用，可参考题目由于是稀疏图，$n$≈$m$，因此没必要在遍历边时提前判断集合a中是否有n个顶点时间复杂度$O(m\text{log}m)$，主要来自排序步骤由于需要对结构体数组排序，因此需要重载<

染色法

用途：

判断二分图

模板：

int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色 // 参数：u表示当前节点，c表示当前点的颜色 bool dfs(int u, int c) { color[u] = c; // 染色 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!color[j]) { if (!dfs(j, 3 - c)) return false; // 用3-c实现交替染色 } else if (color[j] == c) return false; } return true; } bool check() { bool flag = true; for (int i = 1; i <= n; i ++ ) if (!color[i]) if (!dfs(i, 1)) // 这里不需要3-c，因为这里进入的都是未染色的起点，换句话说是森林另一棵树的根 { flag = false; break; } return flag; }

说明：

用邻接表存储图，注意无向图的边数为2m核心思想：一个图是二分图，当且仅当图中不含奇数环（环的边数是奇数）时间复杂度$O(n+m)$

匈牙利算法

用途：

二分图的最大匹配

模板：

int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过 bool find(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; // 标记已遍历 if (!match[j] || find(match[j])) // j未被匹配，或j已经匹配但其配对对象可选其它的匹配 { match[j] = x; return true; } } } return false; } // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i <= n1; i ++ ) { memset(st, false, sizeof st); if (find(i)) res ++ ; }

说明：

用邻接表存储图，但不必存放双向边，只需存储单向边，因此最大边数为M，而不必用2M核心思想： 假设a和b是左边顶点，c和d是右边顶点，a和b都能匹配c，但a还可以匹配d当a匹配c后，b没有右边顶点可匹配a存在另一个可匹配顶点d，因此把a改成匹配d，这时b再匹配c 最坏时间复杂度$O(nm)$，但实际上会远远小于该复杂度

---

P.S. 部分内容来自y总的模板 如果大家有兴趣，可以去Acwing《算法基础课》看看 我在Acwing也分享了一份，欢迎去围观