图论算法

图论算法

图论是 CSP-J/S 复赛的高频考点。共 21 个模板。

← 返回模板库

8.1邻接矩阵存图

二维数组存图，适合稠密图

O(V²) 空间

8.2邻接表存图

vector 存图，适合稀疏图

O(V + E) 空间

8.3链式前向星存图

数组模拟链表，竞赛主流存图方式

O(V + E) 空间

8.4Dijkstra 算法

贪心求单源最短路，适用于非负权图

O((V + E) log V)

8.5SPFA 算法

队列优化的 Bellman-Ford，可处理负权边

O(k × E)

8.6Floyd 算法

多源最短路，三重循环枚举中转点

O(V³)

8.7Prim 算法

贪心求最小生成树，适合稠密图

O(V² 或 (V+E) log V)

8.8Kruskal 算法

边排序 + 并查集，适合稀疏图

O(E log E)

8.9并查集 - 基础

路径压缩 + 按秩合并

O(α(n)) 均摊

8.10并查集 - 带权

维护节点到根的距离，处理偏移关系

O(α(n)) 均摊

8.11拓扑排序

判断有向无环图，确定任务执行顺序

O(V + E)

8.12Tarjan - 强连通分量

一次 DFS 找出所有强连通分量

O(V + E)

8.13Tarjan - 割点

找无向图中的割点（删除后图不连通的点）

O(V + E)

8.14Tarjan - 桥

找无向图中的桥（删除后图不连通的边）

O(V + E)

8.15DFS 序

记录 DFS 进出时间，将子树转化为区间

O(V + E)

8.16树的重心

删除后最大子树最小的节点

O(V)

8.17树的直径

两次 DFS 或树形 DP 求最长路径

O(V)

8.18二分图判定

染色法判断图是否为二分图

O(V + E)

8.19匈牙利算法

二分图最大匹配

O(V × E)

8.20最小环

Floyd 变形，枚举中转点时同时更新答案

O(V³)

8.21负环检测

SPFA 判断图中是否存在负权环

O(k × E)