Graph

自动关联目录:Graph

图是表达"关系"的通用模型。很多看起来不像图的题,建出图来就迎刃而解。

术语

术语含义
顶点 / 边vertex / edge
有向图 / 无向图边有没有方向
度 / 出度 / 入度关联的边数
路径 / 简单路径顶点序列 / 顶点不重复
环起点=终点且长度 > 0
连通 / 强连通无向图任意两点可达 / 有向图互相可达
DAG有向无环图
生成树连通所有顶点且无环的子图(n−1n-1 条边)
权值边上的数值

存储方式

邻接矩阵

int g[N][N];       // g[u][v] = 边权(无边为 INF/0)
  • 查边O(1)O(1)
  • 空间O(n2)O(n^2)
  • 适用:n≤1000n \le 1000,或需要频繁判断"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}); }
  • 空间O(n+m)O(n + m)
  • 遍历某点的所有边O(deg⁡)O(\deg)
  • 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 开销)、内存可控
  • 适合mm 很大(10610^6)或卡常数的场景

选择建议:默认用 vector 邻接表;n>105n > 10^5 且边数多、被卡时间时换前向星。

本目录

章节内容
TraverseDFS / BFS、拓扑排序、连通性

图论算法地图

问题算法复杂度
遍历DFS / BFSO(n+m)O(n+m)
拓扑排序Kahn / DFSO(n+m)O(n+m)
连通分量并查集 / DFSO(n+m)O(n+m)
强连通分量Tarjan / KosarajuO(n+m)O(n+m)
最小生成树Kruskal / PrimO(mlog⁡m)O(m \log m)
单源最短路(非负权)DijkstraO((n+m)log⁡n)O((n+m)\log n)
单源最短路(有负权)Bellman-Ford / SPFAO(nm)O(nm)
多源最短路FloydO(n3)O(n^3)
二分图匹配匈牙利 / 最大流O(nm)O(nm)
网络流Dinic视规模
欧拉路径HierholzerO(n+m)O(n+m)
最近公共祖先倍增 / TarjanO(nlog⁡n)O(n\log n)

建模:把问题变成图

这是图论最难的部分——看出"这其实是个图"。

题目特征建模
"A 能到 B""A 依赖 B"有向边
"状态 A 能变成状态 B"状态为点,转移为边
"不能同时选"补图 / 二分图
"最少步数"BFS(边权为 1)
"代价最小"最短路
"全部连通的最小代价"MST
"分配 / 匹配"二分图匹配 / 网络流

典型例子:

  • 单词接龙 → 字符串为点,能接上就有边 → 最短路
  • 迷宫最少步数 → 格子为点 → BFS
  • 课程安排(有 prerequisite)→ 依赖为边 → 拓扑排序判环
  • 差分约束 → 不等式转成边的最短路

常见坑

  • 有向图忘了加反向边(无向图要加两次)
  • 邻接表没清空(多组数据)
  • 节点编号从 0 还是 1 开始不一致
  • DFS 忘了访问标记 → 指数复杂度或死循环
  • 重边 / 自环没处理(最短路里重边无害,但计数类问题会错)
  • INF 取太小:0x3f3f3f3f 约10910^9,如果最短路可能超过它就会溢出判断。用 long long + 4e18