5058 字
25 分钟
图论算法详解
图论算法详解
图论是计算机科学中最重要的研究领域之一，在OI竞赛中占据着举足轻重的地位。本文将系统性地介绍图论中的核心算法，包括理论基础、算法实现、复杂度分析以及经典应用。
一、图的基本概念
1.1 图的定义
图 G = (V, E) 由顶点集 V 和边集 E 组成。根据边是否有方向，图分为：
- 有向图：边具有方向性，用有序对 (u, v) 表示
- 无向图：边无方向性，用无序对 {u, v} 表示
根据边是否带权值，又分为：
- 带权图：每条边有对应的权值 w(u, v)
- 无权图：可视为所有边权值为 1 的特殊带权图
1.2 图的存储方式
邻接矩阵
使用二维数组 g[u][v] 存储边的信息：
- 对于无权图：
g[u][v] = 1表示存在边，0表示不存在 - 对于带权图：
g[u][v] = w表示边权，INF表示不存在边
优点：查询两点间是否有边的时间复杂度为 O(1) 缺点：空间复杂度 O(V²)，不适合稀疏图
const int MAXN = 1005;const int INF = 0x3f3f3f3f;int g[MAXN][MAXN]; // 邻接矩阵int n, m; // n个顶点，m条边
// 初始化void init() { memset(g, 0x3f, sizeof(g)); for (int i = 1; i <= n; i++) { g[i][i] = 0; // 自环距离为0 }}
// 添加边（无向图）void addEdge(int u, int v, int w) { g[u][v] = w; g[v][u] = w;}邻接表
使用向量数组存储每个顶点的邻居信息，适合稀疏图。
优点：空间复杂度 O(V + E)，适合稀疏图 缺点：查询两点间是否有边需要 O(度数) 时间
const int MAXN = 100005;struct Edge { int to, w; // 终点，权值 Edge(int to, int w) : to(to), w(w) {}};
vector<Edge> g[MAXN]; // 邻接表int n, m;
// 添加有向边void addEdge(int u, int v, int w) { g[u].push_back(Edge(v, w));}
// 添加无向边void addUndirectedEdge(int u, int v, int w) { g[u].push_back(Edge(v, w)); g[v].push_back(Edge(u, w));}链式前向星（竞赛常用）
使用静态数组模拟链表，常用于竞赛中，效率高于 vector。
const int MAXN = 100005;const int MAXM = 500005;
struct Edge { int to, w, next;} edge[MAXM];
int head[MAXN], cnt;
void init() { memset(head, -1, sizeof(head)); cnt = 0;}
void addEdge(int u, int v, int w) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++;}
// 遍历顶点u的所有边for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; // 处理边 u -> v，权值为 w}二、图的遍历
2.1 深度优先搜索（DFS）
DFS 采用递归或栈的方式，沿着一条路径尽可能深入，直到无法继续为止，然后回溯。
算法流程：
- 从起点开始标记为已访问
- 递归访问所有未访问的邻居
- 回溯到上一层继续搜索
时间复杂度：O(V + E)
bool vis[MAXN];
void dfs(int u) { vis[u] = true; cout << u << " "; // 访问顶点u
// 遍历所有邻居 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!vis[v]) { dfs(v); } }}
// 处理非连通图void dfsAll() { memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) { if (!vis[i]) { dfs(i); } }}应用场景：
- 连通性判断
- 环检测
- 拓扑排序
- 强连通分量
2.2 广度优先搜索（BFS）
BFS 采用队列，按层次逐层访问顶点，先访问距离起点近的顶点。
算法流程：
- 起点入队并标记为已访问
- 队首元素出队，访问所有未访问的邻居
- 邻居入队并标记，重复步骤2直到队列为空
时间复杂度：O(V + E)
int dist[MAXN]; // 距离数组
void bfs(int s) { queue<int> q; memset(vis, false, sizeof(vis)); memset(dist, 0x3f, sizeof(dist));
q.push(s); vis[s] = true; dist[s] = 0;
while (!q.empty()) { int u = q.front(); q.pop();
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!vis[v]) { vis[v] = true; dist[v] = dist[u] + 1; q.push(v); } } }}应用场景：
- 无权图最短路
- 层次遍历
- 二分图判定
- 最小步数问题
三、最短路算法
3.1 Dijkstra算法
Dijkstra 算法用于求解非负权图的单源最短路径。
算法原理：
- 初始化源点距离为0，其余为无穷大
- 选择未确定最短路的距离最小的顶点u
- 用u松弛其所有邻居的距离
- 标记u为已确定，重复2-3直到所有顶点确定
正确性证明：反证法。假设第一个被错误标记的顶点为u，设s到u的真实最短路径为 s→…→x→y→…→u，其中x是最后一个已确定的顶点。由于边权非负，dist[y] ≤ 真实最短路径长度 ≤ dist[u]，矛盾。
时间复杂度：
- 朴素实现：O(V²)
- 优先队列优化：O((V + E)logV)
const int MAXN = 100005;const int INF = 0x3f3f3f3f;
int dist[MAXN];bool vis[MAXN];
// 朴素Dijkstra，适合稠密图void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] = 0;
for (int i = 1; i <= n; i++) { int u = -1, minDist = INF; // 找到未访问的距离最小的顶点 for (int j = 1; j <= n; j++) { if (!vis[j] && dist[j] < minDist) { minDist = dist[j]; u = j; } }
if (u == -1) break; vis[u] = true;
// 松弛操作 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } }}
// 堆优化Dijkstra，适合稀疏图struct Node { int v, dist; bool operator<(const Node& other) const { return dist > other.dist; // 小根堆 }};
void dijkstraHeap(int s) { priority_queue<Node> pq; memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis));
dist[s] = 0; pq.push({s, 0});
while (!pq.empty()) { Node cur = pq.top(); pq.pop();
int u = cur.v; if (vis[u]) continue; vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({v, dist[v]}); } } }}3.2 Bellman-Ford算法
Bellman-Ford 算法可以处理负权边，并能检测负权环。
算法原理： 进行 V-1 轮松弛操作，每轮遍历所有边，如果 dist[u] + w(u,v) < dist[v]，则更新 dist[v]。
正确性证明：最短路径最多包含 V-1 条边，第k轮松弛后，所有最多k条边的最短路都被正确计算。
负环检测：如果第V轮还能松弛，则存在负环。
时间复杂度：O(VE)
struct EdgeBF { int u, v, w;};
EdgeBF edges[MAXM];int dist[MAXN];int m; // 边数
bool bellmanFord(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] = 0;
// V-1轮松弛 for (int i = 1; i <= n - 1; i++) { for (int j = 0; j < m; j++) { int u = edges[j].u; int v = edges[j].v; int w = edges[j].w; if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } }
// 检测负环 for (int j = 0; j < m; j++) { int u = edges[j].u; int v = edges[j].v; int w = edges[j].w; if (dist[u] != INF && dist[u] + w < dist[v]) { return false; // 存在负环 } }
return true;}3.3 SPFA算法
SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本。
算法原理： 只有当顶点u的距离被更新时，才用u去松弛其邻居。使用队列维护待松弛的顶点。
时间复杂度：
- 平均：O(kE)，k为常数约为2
- 最坏：O(VE)
int dist[MAXN];bool inQueue[MAXN];int cnt[MAXN]; // 入队次数，用于检测负环
bool spfa(int s) { queue<int> q; memset(dist, 0x3f, sizeof(dist)); memset(inQueue, false, sizeof(inQueue)); memset(cnt, 0, sizeof(cnt));
dist[s] = 0; q.push(s); inQueue[s] = true; cnt[s]++;
while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false;
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inQueue[v]) { q.push(v); inQueue[v] = true; cnt[v]++; // 如果入队超过n次，存在负环 if (cnt[v] > n) return false; } } } } return true;}3.4 Floyd算法
Floyd 算法用于求解所有点对之间的最短路径。
算法原理：
动态规划思想。设 dp[k][i][j] 表示只使用前k个顶点作为中转点时，i到j的最短路径。
状态转移：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
由于第一维可以滚动优化掉，最终为：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
时间复杂度：O(V³)
int dist[MAXN][MAXN];
void 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] = INF; } }
// 读入边 for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; dist[u][v] = min(dist[u][v], w); // 处理重边 }
// Floyd核心 for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][k] != INF && dist[k][j] != INF) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } }}四、最小生成树
最小生成树（MST）是连通带权无向图的一个子图，包含所有顶点且边权和最小的树。
4.1 Kruskal算法
算法思想：贪心 + 并查集。将所有边按权值从小到大排序，依次考虑每条边，如果边的两端不在同一连通分量，则加入该边。
正确性证明：使用切割定理。设当前生成森林为F，最小生成树为T，考虑F中不在T中的最小边e=(u,v)。在T中u到v的路径上必存在一条边e’连接F的两个连通分量，且w(e’) ≥ w(e)，用e替换e’得到权值不大于T的生成树。
时间复杂度：O(ElogE)，主要是排序
struct EdgeKruskal { int u, v, w; bool operator<(const EdgeKruskal& other) const { return w < other.w; }};
EdgeKruskal edges[MAXM];int parent[MAXN];
// 并查集void initUF(int n) { for (int i = 1; i <= n; i++) { parent[i] = i; }}
int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x];}
bool unite(int x, int y) { int px = find(x); int py = find(y); if (px == py) return false; parent[px] = py; return true;}
int kruskal() { sort(edges, edges + m); initUF(n);
int mstWeight = 0; int edgeCount = 0;
for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; int w = edges[i].w;
if (unite(u, v)) { mstWeight += w; edgeCount++; if (edgeCount == n - 1) break; // 已经找到n-1条边 } }
if (edgeCount < n - 1) return -1; // 图不连通 return mstWeight;}4.2 Prim算法
算法思想：从任意顶点开始，每次选择与当前生成树相连的最小权值边，将新顶点加入树。
时间复杂度：
- 朴素实现：O(V²)
- 堆优化：O(ElogV)
int dist[MAXN]; // 顶点到MST的最小距离bool inMST[MAXN];
int prim() { memset(dist, 0x3f, sizeof(dist)); memset(inMST, false, sizeof(inMST));
int mstWeight = 0; dist[1] = 0; // 从顶点1开始
for (int i = 1; i <= n; i++) { int u = -1, minDist = INF; // 找到不在MST中距离最小的顶点 for (int j = 1; j <= n; j++) { if (!inMST[j] && dist[j] < minDist) { minDist = dist[j]; u = j; } }
if (u == -1) return -1; // 图不连通
inMST[u] = true; mstWeight += dist[u];
// 更新邻居到MST的距离 for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; if (!inMST[v] && w < dist[v]) { dist[v] = w; } } }
return mstWeight;}
// 堆优化版本int primHeap() { priority_queue<Node> pq; memset(dist, 0x3f, sizeof(dist)); memset(inMST, false, sizeof(inMST));
int mstWeight = 0; dist[1] = 0; pq.push({1, 0});
while (!pq.empty()) { Node cur = pq.top(); pq.pop();
int u = cur.v; if (inMST[u]) continue;
inMST[u] = true; mstWeight += dist[u];
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; if (!inMST[v] && w < dist[v]) { dist[v] = w; pq.push({v, dist[v]}); } } }
return mstWeight;}五、拓扑排序
拓扑排序是对有向无环图（DAG）的顶点进行线性排序，使得对于每条边 (u, v)，u 在排序中都在 v 之前。
Kahn算法（基于BFS）：
- 统计每个顶点的入度
- 将入度为0的顶点入队
- 队首元素出队，加入结果，将其邻居入度减1
- 若邻居入度变为0，则入队
- 重复3-4直到队列为空
时间复杂度：O(V + E)
int inDegree[MAXN];int topoOrder[MAXN];int topoIdx;
bool topoSort() { queue<int> q; memset(inDegree, 0, sizeof(inDegree)); topoIdx = 0;
// 统计入度 for (int u = 1; u <= n; u++) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; inDegree[v]++; } }
// 入度为0的顶点入队 for (int i = 1; i <= n; i++) { if (inDegree[i] == 0) { q.push(i); } }
while (!q.empty()) { int u = q.front(); q.pop(); topoOrder[topoIdx++] = u;
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; inDegree[v]--; if (inDegree[v] == 0) { q.push(v); } } }
return topoIdx == n; // 如果不等于n，说明有环}
// DFS版本int dfn[MAXN], low[MAXN];int timestamp;bool inStack[MAXN];bool hasCycle;
void topoSortDFS(int u) { vis[u] = true; inStack[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!vis[v]) { topoSortDFS(v); } else if (inStack[v]) { hasCycle = true; // 存在回边，有环 return; } }
inStack[u] = false; topoOrder[--topoIdx] = u; // 逆序插入}六、并查集
并查集（Union-Find）用于处理不相交集合的合并和查询问题。
核心操作：
find(x)：查找x所在集合的代表元素unite(x, y)：合并x和y所在的集合
优化技术：
- 路径压缩：在find过程中将路径上的所有节点直接连到根
- 按秩合并：将深度小的树合并到深度大的树上
时间复杂度：接近 O(1)，准确地说是 O(α(n))，其中α是反阿克曼函数
int parent[MAXN];int rank_[MAXN]; // 秩（树的深度上界）
void initUF(int n) { for (int i = 1; i <= n; i++) { parent[i] = i; rank_[i] = 0; }}
// 路径压缩int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x];}
// 按秩合并bool unite(int x, int y) { int px = find(x); int py = find(y);
if (px == py) return false;
if (rank_[px] < rank_[py]) { parent[px] = py; } else if (rank_[px] > rank_[py]) { parent[py] = px; } else { parent[py] = px; rank_[px]++; }
return true;}
bool isConnected(int x, int y) { return find(x) == find(y);}
// 带权并查集（用于关系型问题）int dist[MAXN]; // 到父节点的距离
int findWeighted(int x) { if (parent[x] != x) { int root = findWeighted(parent[x]); dist[x] += dist[parent[x]]; // 路径压缩时累加距离 parent[x] = root; } return parent[x];}七、二分图判定与匹配
7.1 二分图判定
定义：顶点可以分为两个不相交的集合，使得所有边的两端分别属于不同集合。
判定方法：DFS/BFS染色法。如果能够用两种颜色给所有顶点染色，使得相邻顶点颜色不同，则是二分图。
原理：二分图等价于不含奇数环的图。
int color[MAXN]; // 0未染色，1/2表示两种颜色
bool dfsColor(int u, int c) { color[u] = c;
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (color[v] == 0) { if (!dfsColor(v, 3 - c)) return false; // 染另一种颜色 } else if (color[v] == c) { return false; // 相邻顶点同色，不是二分图 } }
return true;}
bool isBipartite() { memset(color, 0, sizeof(color)); for (int i = 1; i <= n; i++) { if (color[i] == 0) { if (!dfsColor(i, 1)) return false; } } return true;}7.2 二分图最大匹配（匈牙利算法）
问题：找到最多的边数，使得这些边没有公共顶点。
算法思想：对于左部的每个顶点，尝试为其找到一个匹配点。如果匹配点已经被匹配，则尝试为其当前匹配重新找一个匹配点（增广路）。
时间复杂度：O(VE)
int match[MAXN]; // match[v]表示右部顶点v的匹配点bool used[MAXN]; // 本轮是否已尝试过
bool dfsMatch(int u) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!used[v]) { used[v] = true; // v未匹配或v的匹配点可以换 if (match[v] == 0 || dfsMatch(match[v])) { match[v] = u; return true; } } } return false;}
int hungarian() { memset(match, 0, sizeof(match)); int result = 0;
for (int i = 1; i <= n; i++) { // 枚举左部顶点 memset(used, false, sizeof(used)); if (dfsMatch(i)) result++; }
return result;}八、强连通分量
8.1 Tarjan算法
定义：有向图中的极大强连通子图称为强连通分量（SCC）。
算法原理：
dfn[u]：顶点u的DFS时间戳low[u]：u及其子树能够回溯到的最早祖先的时间戳- 如果
dfn[u] == low[u]，则u是某个SCC的根
时间复杂度：O(V + E)
int dfn[MAXN], low[MAXN];int timestamp;int stk[MAXN], top;bool inStack[MAXN];int sccId[MAXN], sccCnt; // 每个顶点所属的SCC编号
void tarjan(int u) { dfn[u] = low[u] = ++timestamp; stk[++top] = u; inStack[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (inStack[v]) { low[u] = min(low[u], dfn[v]); } }
// u是SCC的根 if (dfn[u] == low[u]) { sccCnt++; int v; do { v = stk[top--]; inStack[v] = false; sccId[v] = sccCnt; } while (v != u); }}
void findSCC() { memset(dfn, 0, sizeof(dfn)); memset(inStack, false, sizeof(inStack)); timestamp = 0; top = 0; sccCnt = 0;
for (int i = 1; i <= n; i++) { if (!dfn[i]) { tarjan(i); } }}8.2 Kosaraju算法
算法步骤：
- 对原图进行DFS，按结束时间逆序排列顶点
- 构造反向图
- 按第1步的顺序对反向图进行DFS，每次DFS访问的顶点构成一个SCC
vector<int> order;bool vis[MAXN];vector<int> reverseG[MAXN];
void dfs1(int u) { vis[u] = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!vis[v]) dfs1(v); } order.push_back(u);}
void dfs2(int u, int id) { sccId[u] = id; for (int v : reverseG[u]) { if (sccId[v] == 0) dfs2(v, id); }}
void kosaraju() { // 第一次DFS memset(vis, false, sizeof(vis)); order.clear(); for (int i = 1; i <= n; i++) { if (!vis[i]) dfs1(i); }
// 构造反向图 for (int u = 1; u <= n; u++) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; reverseG[v].push_back(u); } }
// 第二次DFS memset(sccId, 0, sizeof(sccId)); sccCnt = 0; reverse(order.begin(), order.end()); for (int u : order) { if (sccId[u] == 0) { dfs2(u, ++sccCnt); } }}九、经典OI题目应用
9.1 最短路应用：[USACO] Navigation Nightmare
问题：给定一些相对位置关系，查询两点间的距离。
解法：带权并查集。维护每个节点到根的距离向量。
9.2 最小生成树应用：[POI] 道路建设
问题：n个城市，m条可建道路，每条道路有建设成本，求使所有城市连通的最小成本。
解法：标准Kruskal算法求解MST。
9.3 拓扑排序应用：[NOI] 食物链
问题：给定食物链关系，判断是否存在矛盾（环）。
解法：建有向图，进行拓扑排序。如果无法完成排序，则存在环。
9.4 强连通分量应用：[USACO] 受欢迎的牛
问题：有n头牛，给定m个崇拜关系（a崇拜b），崇拜关系可以传递。求有多少头牛被所有牛崇拜。
解法：
- 用Tarjan求出所有SCC
- 缩点建立SCC之间的DAG
- 如果有且仅有一个出度为0的SCC，答案为该SCC的大小；否则答案为0
int outDegree[MAXN]; // SCC的出度
int solve() { findSCC();
// 统计每个SCC的出度 memset(outDegree, 0, sizeof(outDegree)); for (int u = 1; u <= n; u++) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (sccId[u] != sccId[v]) { outDegree[sccId[u]]++; } } }
// 找出度为0的SCC int zeroOutDegree = 0; int targetSCC = 0; for (int i = 1; i <= sccCnt; i++) { if (outDegree[i] == 0) { zeroOutDegree++; targetSCC = i; } }
if (zeroOutDegree != 1) return 0;
// 统计该SCC的顶点数 int ans = 0; for (int i = 1; i <= n; i++) { if (sccId[i] == targetSCC) ans++; }
return ans;}9.5 二分图匹配应用：[匈牙利游戏]
问题：n个任务，m个工人，每个工人能完成某些任务，求最多能完成多少任务。
解法：建立二分图，左部为工人，右部为任务，用匈牙利算法求最大匹配。
9.6 网络流应用：最大流问题
虽然本文未详细介绍网络流，但需要知道：
- 最大流：Ford-Fulkerson方法、Dinic算法
- 最小割：最大流最小割定理
- 费用流：最小费用最大流
十、总结与建议
算法选择指南
| 问题类型 | 推荐算法 | 适用条件 |
|---|---|---|
| 单源最短路（非负权） | Dijkstra堆优化 | 稀疏图 |
| 单源最短路（有负权） | SPFA | 无负环 |
| 单源最短路（负环检测） | Bellman-Ford | 需要检测负环 |
| 全源最短路 | Floyd | 顶点数较少(≤500) |
| 最小生成树（稀疏图） | Kruskal | 边较少 |
| 最小生成树（稠密图） | Prim | 边较多 |
| 拓扑排序 | Kahn(BFS) | 简单清晰 |
| 强连通分量 | Tarjan | 一次DFS |
| 二分图判定 | DFS染色 | 简单高效 |
| 二分图匹配 | 匈牙利算法 | 经典算法 |
学习建议
- 掌握基础：先熟练掌握图的存储和遍历
- 理解原理：不要只记模板，要理解算法的正确性证明
- 多做练习：在OJ上刷题巩固（推荐洛谷、Codeforces）
- 注意细节：边界条件、特殊情况（自环、重边、非连通图）
- 优化技巧：学会时间和空间的权衡
常见陷阱
- Dijkstra不能处理负权边
- Floyd的循环顺序不能错（k-i-j）
- SPFA在特殊图上会退化到O(VE)
- 并查集路径压缩不能用非递归写法随意优化
- 拓扑排序仅适用于DAG
掌握这些图论算法，足以应对大部分OI竞赛中的图论问题。持续练习，深入理解，方能在竞赛中游刃有余！