Graph
自动关联目录:Graph
图是表达"关系"的通用模型。很多看起来不像图的题,建出图来就迎刃而解。
术语
| 术语 | 含义 |
|---|---|
| 顶点 / 边 | vertex / edge |
| 有向图 / 无向图 | 边有没有方向 |
| 度 / 出度 / 入度 | 关联的边数 |
| 路径 / 简单路径 | 顶点序列 / 顶点不重复 |
| 环 | 起点=终点且长度 > 0 |
| 连通 / 强连通 | 无向图任意两点可达 / 有向图互相可达 |
| DAG | 有向无环图 |
| 生成树 | 连通所有顶点且无环的子图( 条边) |
| 权值 | 边上的数值 |
存储方式
邻接矩阵
int g[N][N]; // g[u][v] = 边权(无边为 INF/0)- 查边
- 空间
- 适用:,或需要频繁判断"u,v 是否有边"
邻接表(最常用)
vector<pair<int, int>> g[N]; // g[u] = {(v, w), ...}
void add(int u, int v, int w) { g[u].push_back({v, w}); }- 空间
- 遍历某点的所有边
- 99% 的情况用它
链式前向星(数组模拟邻接表)
int head[N], to[M], nxt[M], w[M], ecnt = 0;
void add(int u, int v, int _w) {
to[ecnt] = v; w[ecnt] = _w;
nxt[ecnt] = head[u]; head[u] = ecnt++;
}
// 遍历
for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e]; /* ... */ }- 更快(无
vector开销)、内存可控 - 适合 很大()或卡常数的场景
选择建议:默认用 vector 邻接表; 且边数多、被卡时间时换前向星。
本目录
| 章节 | 内容 |
|---|---|
| Traverse | DFS / BFS、拓扑排序、连通性 |
图论算法地图
| 问题 | 算法 | 复杂度 |
|---|---|---|
| 遍历 | DFS / BFS | |
| 拓扑排序 | Kahn / DFS | |
| 连通分量 | 并查集 / DFS | |
| 强连通分量 | Tarjan / Kosaraju | |
| 最小生成树 | Kruskal / Prim | |
| 单源最短路(非负权) | Dijkstra | |
| 单源最短路(有负权) | Bellman-Ford / SPFA | |
| 多源最短路 | Floyd | |
| 二分图匹配 | 匈牙利 / 最大流 | |
| 网络流 | Dinic | 视规模 |
| 欧拉路径 | Hierholzer | |
| 最近公共祖先 | 倍增 / Tarjan |
建模:把问题变成图
这是图论最难的部分——看出"这其实是个图"。
| 题目特征 | 建模 |
|---|---|
| "A 能到 B""A 依赖 B" | 有向边 |
| "状态 A 能变成状态 B" | 状态为点,转移为边 |
| "不能同时选" | 补图 / 二分图 |
| "最少步数" | BFS(边权为 1) |
| "代价最小" | 最短路 |
| "全部连通的最小代价" | MST |
| "分配 / 匹配" | 二分图匹配 / 网络流 |
典型例子:
- 单词接龙 → 字符串为点,能接上就有边 → 最短路
- 迷宫最少步数 → 格子为点 → BFS
- 课程安排(有 prerequisite)→ 依赖为边 → 拓扑排序判环
- 差分约束 → 不等式转成边的最短路
常见坑
- 有向图忘了加反向边(无向图要加两次)
- 邻接表没清空(多组数据)
- 节点编号从 0 还是 1 开始不一致
- DFS 忘了访问标记 → 指数复杂度或死循环
- 重边 / 自环没处理(最短路里重边无害,但计数类问题会错)
- INF 取太小:
0x3f3f3f3f约,如果最短路可能超过它就会溢出判断。用long long+4e18
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/c8842ad8.html
更新于:2026年11月16日