图论核心算法全攻略（含 10 大算法 + 场景速选）图论是数据结构与算法优化的核心模块，也是笔试、面试、期末考试的高频考点。很多学习者的核心痛点是：面对一道图论题，既分不清 “拓扑排序 / 并查集 / DFS” 该选谁，也不知道除了基础 6 大算法外，还有哪些核心算法适配特殊场景。
本文将系统梳理10 类图论核心算法（包含你指定的拓扑排序、Floyd、Dijkstra、Prim、DFS/BFS、并查集 6 个必选算法，额外补充 4 类高频核心算法），按 “场景特征→最优算法→选择原因→避坑指南” 的逻辑拆解，帮你建立 “看场景选算法” 的思维，无论是期末复习还是实战刷题都能直接套用。
一、图论算法选择的底层逻辑（先记这 3 步）选择图论算法无需死记硬背，只需按以下 3 步判断，就能快速锁定最优解：
定目标：明确问题核心诉求（排序 / 判环？最短路径？连通性？最小生成树？网络流？）；看图特性：区分图的类型（有向 / 无向？稠密 / 稀疏？边权非负 / 含负权？是否有环？）；看数据规模：顶点数 n、边数 m 的大小（决定算法效率是否达标，比如 n>100 时 Floyd 会超时）。二、全场景算法选择对照表（核心精华）核心场景典型题型特征最优算法包含关系选择原因典型例题关键注意点有向图排序 + 环检测1. 有向图；2. 需按依赖关系排序；3. 需判断是否有环（DAG 验证）拓扑排序（Kahn）必选1. 时间复杂度 O (n+m)，适配 n≤1000 的场景；2. 迭代版（队列）避免栈溢出；3. 天然支持环检测课程表、拓扑排序（DS toplogical sort v1）1. 1 基顶点转 0 基处理；2. 结果长度≠顶点数 = 有环；3. 入度统计不能遗漏多源最短路径查询1. 任意两点间最短路径；2. n≤100（稠密图）；3. 允许负权边（无负权环）Floyd-Warshall必选1. 实现最简单（三重循环）；2. 一次性生成所有点对结果；3. O (n³) 仅 n≤100 可行最短路径（多源查询版）1. INF 选 10000 避免溢出；2. 循环顺序 k→i→j；3. 松弛前判可达单源最短路径（边权非负）1. 单个起点到所有 / 指定终点的最短路径；2. 边权非负；3. n≤200（或堆优化适配更大 n）Dijkstra必选1. 贪心策略效率高（基础版 O (n²)，堆优化 O (m log n)）；2. 边权非负时无更优解畅通工程 3、单源最短路径1. 边权非负是前提；2. 邻接表版适配稀疏图；3. 无向图双向加边最小生成树（稠密无向图）1. 无向图；2. 连接所有顶点且总边权最小；3. 稠密图（边数多，n≤1000）Prim必选1. 基础版 O (n²) 适配稠密图；2. 无需排序边，实现更简洁；3. 天然支持连通性判断公路村村通、畅通工程 21. dist 数组是 “到 MST 的最小边权”（区别 Dijkstra）；2. 用访问顶点数判连通连通分量遍历 / 统计（需顶点）1. 无向图；2. 需输出连通分量具体顶点；3. 需按指定顺序遍历DFS/BFS必选1. 直观易实现，可控制遍历顺序；2. O (n+m) 适配 n≤1000；3. 兼顾遍历和统计列出连通集1. 邻接表排序保证编号递增；2. BFS 入队时标记访问；3. 无向图双向加边连通性快速查询（大规模）1. 仅判断两点连通 / 统计分量数；2. 大规模数据（n≤10000）；3. 无需输出具体顶点并查集（路径压缩 + 秩合）必选1. find/union 近似 O (1)，效率远超 DFS/BFS；2. 代码简洁，适配海量边畅通工程 1、朋友圈1. 合并前先找根节点；2. 必须路径压缩；3. 统计分量数需调用 find最小生成树（稀疏无向图）1. 无向图；2. 连接所有顶点且总边权最小；3. 稀疏图（边数 m
核心优势迭代版（队列 + 入度）比递归版更稳定，避免顶点数多导致的栈溢出；时间复杂度 O (n+m)，适配绝大多数高校期末题的 n≤1000 场景；天然支持环检测（结果长度 < 顶点数 = 有环），无需额外逻辑。避坑指南顶点编号：题目常给 1 基顶点，代码中统一转 0 基处理（避免数组越界），输出时再转回 1 基；入度统计：遍历邻接表时，对每个 u 的邻接顶点 v，必须执行inDegree[v]++，遗漏会导致排序错误；判环逻辑：不要仅判断队列是否为空，必须用「结果长度 = 顶点数」验证无环。2. Floyd-Warshall（多源最短路径）什么时候用？需「一次性求任意两点最短路径」，且顶点数 n≤100（稠密图），允许负权边（但无负权环），比如：小范围地图的所有点对最短路径查询。
核心优势实现最简单的图论算法之一，仅需三重循环，无需复杂数据结构；一次性生成所有点对结果，适配批量查询场景（比如连续查询 10 组点对路径）。避坑指南INF 取值：绝对不能用Integer.MAX_VALUE（INF+INF 会溢出为负数），选 “略大于题目最大路径和” 的值（如 10000）；循环顺序：必须先枚举中间点 k，再枚举起点 i、终点 j（k→i→j），顺序错则松弛逻辑完全失效；松弛前判可达：必须先判断dist[i][k] < INF && dist[k][j] < INF，否则会用无效值更新路径。3. Dijkstra（单源最短路径，边权非负）什么时候用？仅需「单个起点到所有 / 指定终点的最短路径」，且边权非负，比如：从北京到上海的最短公路距离、网络中核心节点到其他节点的最小延迟。
核心优势贪心策略保证最优解（边权非负时），基础版 O (n²) 适配 n≤200，堆优化版 O (m log n) 适配更大 n；邻接表版比邻接矩阵版更省内存，适配稀疏图（边数少）。避坑指南边权限制：有负权边时绝对不能用（贪心策略失效），需改用 SPFA；访问标记：BFS 版 Dijkstra 需在入队时标记访问，而非出队时（避免重复入队）；无向图处理：将无向边视为双向有向边，邻接表中同时添加 u→v 和 v→u。4. Prim（最小生成树，稠密无向图）什么时候用？无向图中「连接所有顶点且总边权最小」，且是稠密图（边数多），比如：村村通公路（村庄多、道路密）、电网布线（节点密集）。
核心优势基础版 O (n²) 适配稠密图，比 Kruskal 更高效（无需排序边）；天然支持连通性判断：若最终加入 MST 的顶点数≠n，说明图不连通。避坑指南关键区别：Prim 的dist数组是「顶点到 MST 的最小边权」，而非 Dijkstra 的「到起点的距离」，切勿混淆；起点选择：任选一个顶点（如 1）作为起点，最终 MST 总权值不变；无向图处理：必须双向添加边，否则会漏连连通关系。5. DFS/BFS（连通分量遍历 / 统计）什么时候用？需要「输出连通分量具体顶点」或「按指定顺序遍历图」，比如：列出所有连通的村庄、按编号递增顺序遍历图的连通区域。
核心优势直观易实现，可精准控制遍历顺序（比如对邻接表排序实现编号递增访问）；既能统计连通分量数，又能输出每个分量的具体顶点，兼顾 “统计” 和 “展示”。避坑指南遍历顺序：题目要求 “按编号递增访问邻接顶点” 时，需对每个顶点的邻接表执行Collections.sort()；BFS 标记时机：必须在入队时标记visited[v] = true，而非出队时（避免重复入队导致死循环）；多组数据：每组数据需重新初始化visited数组，避免前一组数据的标记影响结果。6. 并查集（连通性快速查询）什么时候用？仅需「判断两点是否连通」或「统计连通分量数」，且数据规模大（n≤10000），比如：畅通工程（计算需建设的最少道路数）、大规模社交网络判断好友关系。
核心优势路径压缩 + 按秩合并后，find/union 操作的时间复杂度近似 O (1)，效率远超 DFS/BFS；代码简洁，内存占用低，适配海量边处理（比如 10 万条边）。避坑指南合并逻辑：必须先调用find(a)和find(b)找到根节点，再合并根节点（而非直接合并原顶点）；路径压缩：查找时必须执行parent[x] = find(parent[x])，否则效率会骤降为 O (n)；分量统计：统计连通分量数时，需调用find(i)验证是否为根节点，而非直接判断parent[i] == i（路径未压缩时会出错）。（二）补充算法：4 大高频核心（拓展提分）1. Kruskal（最小生成树，稀疏无向图）什么时候用？无向图中「连接所有顶点且总边权最小」，且是稀疏图（边数少，比如 n=1000 但 m=2000），比如：城市间建高铁（仅少数城市间有线路）。
核心思路步骤 1：将所有边按权值升序排序；步骤 2：用并查集遍历边，若边的两个顶点不在同一连通分量，则选中该边并合并分量；步骤 3：直到选中 n-1 条边（生成 MST）或遍历完所有边（图不连通）。避坑指南边排序：必须按权值升序排序（保证选的是最小权值边）；判环逻辑：用并查集判断边的两个顶点是否连通，连通则跳过（避免环）；终止条件：选中 n-1 条边即可终止（MST 恰好有 n-1 条边），无需遍历所有边。2. Bellman-Ford/SPFA（单源最短路径，负权边 / 判环）什么时候用？单源最短路径场景中包含负权边，或需要判断是否存在负权环，比如：带手续费的路径规划（手续费为负权）、验证图中是否有负权环（路径长度无限减小）。
核心思路Bellman-Ford：对所有边松弛 n-1 次（n 为顶点数），若第 n 次仍能松弛，则存在负权环；SPFA（优化版）：用队列存储待松弛的顶点，仅松弛有更新的顶点，效率比 Bellman-Ford 高 10 倍以上。避坑指南负权环检测：SPFA 中若某个顶点入队次数 > n，则说明存在负权环；效率优化：SPFA 中可跳过已确定最短路径的顶点（或用 SLF 优化队列）；适用场景：仅在有负权边时使用，无负权边时优先选 Dijkstra（效率更高）。3. Tarjan（强连通分量 / 割点割边）什么时候用？有向图找强连通分量（顶点间互相可达），比如：压缩有向图为 DAG；无向图找割点（删除后图连通分量增加）/ 割边（桥，删除后图连通分量增加），比如：网络故障排查（找关键节点 / 链路）。核心思路用 DFS 遍历图，维护两个数组：dfn[u]：顶点 u 的访问时间戳（首次访问顺序）；low[u]：顶点 u 能到达的最小时间戳（回溯时更新）；强连通分量：若low[u] == dfn[u]，则 u 是强连通分量的根节点；割点：若low[v] >= dfn[u]（v 是 u 的子节点），则 u 是割点；割边：若low[v] > dfn[u]，则 u→v 是割边。避坑指南递归栈处理：需用栈存储遍历过的顶点，找到强连通分量时弹出栈内顶点；无向图处理：遍历邻接顶点时需跳过父节点（避免回边干扰）；时间戳初始化：dfn和low数组初始化为 - 1，避免重复访问。4. Fleury 算法（欧拉路径 / 回路，一笔画）什么时候用？判断无向 / 有向图是否存在欧拉路径 / 回路，或输出具体的一笔画路径，比如：一笔画游戏、路径规划（不重复走边）。
核心前提（先判断是否存在）无向图：欧拉回路：所有顶点度数为偶数；欧拉路径：恰好 2 个顶点度数为奇数（起点和终点）；有向图：欧拉回路：所有顶点入度 = 出度；欧拉路径：恰好 1 个顶点入度 = 出度 - 1（起点），1 个顶点入度 = 出度 + 1（终点）。核心思路从起点出发，贪心选择非桥边（除非无其他边可选），遍历并删除该边；递归遍历邻接顶点，直到遍历完所有边，回溯时记录路径（最终反转路径即为结果）。避坑指南先判条件：必须先验证欧拉路径 / 回路的度数条件，否则直接遍历会无效；桥的判断：优先选非桥边（避免提前断开图），无其他边时再选桥；路径记录：回溯时记录顶点，最终反转路径（因为递归是从终点回溯到起点）。四、期末速记：图论算法选择口诀（精华）排序判环选拓扑，入度队列判环忙；多源最短用 Floyd，三重循环别乱序；单源非负 Dijkstra，贪心松弛效率强；稠密 MST 选 Prim，稀疏 MST Kruskal；连通遍历 DFS/BFS，连通查询并查集；负权最短 SPFA，判环入队次数量；强连通用 Tarjan，欧拉路径看度数；最大流选 Dinic，分层增广路通畅。五、总结图论算法的选择本质是「场景匹配」：
必选 6 大算法覆盖了 80% 的基础场景（排序、最短路径、连通性、最小生成树），是期末复习的核心；补充 4 大算法适配 20% 的特殊场景（负权边、稀疏图、强连通、一笔画），是提分和实战的关键。