图算法

一句话说明

图算法本质上是在一堆“点和关系”里回答四类问题：能不能到、最短多远、怎样最低成本连起来、依赖顺序怎么排。

先判断题目属于哪一类

flowchart TD
    A["看到点、边、路径、依赖、联通"] --> B{"题目在问什么?"}
    B -- "能否到达 / 连通块 / 所有路径" --> C["遍历：DFS / BFS"]
    B -- "最少步数 / 最短距离" --> D["最短路"]
    B -- "最小成本把所有点连起来" --> E["最小生成树"]
    B -- "先做谁后做谁 / 是否有环" --> F["拓扑排序"]
    B -- "图里有哪些强结构" --> G["强连通分量 / 二分图 / 桥和割点"]

最常见选择题

刷题时先看这张分流表

图算法知识地图

flowchart LR
    A["图算法"] --> B["图的基础"]
    A --> C["遍历"]
    A --> D["最短路径"]
    A --> E["生成树 / DAG"]
    A --> F["连通性"]
    A --> G["高级专题"]

    B --> B1["表示方式"]
    C --> C1["DFS"]
    C --> C2["BFS"]
    D --> D1["单源最短路"]
    D --> D2["多源最短路"]
    E --> E1["MST"]
    E --> E2["拓扑排序"]
    F --> F1["SCC / 桥 / 割点 / 二分图"]
    G --> G1["0-1 BFS / 欧拉路 / 网络流"]

📚 目录结构

1. 图的基础

• 图的表示：邻接矩阵、邻接表、边集数组怎么选

2. 图的遍历

• DFS与BFS：什么时候该“走到底”，什么时候该“按层推”

3. 最短路径

• 单源最短路径：BFS、0-1 BFS、Dijkstra、Bellman-Ford 的选择逻辑
• 多源最短路径：Floyd-Warshall 与全源最短路

4. 最小生成树与拓扑排序

• 最小生成树：Kruskal、Prim
• 拓扑排序：Kahn、DFS 实现

5. 连通性问题

• 强连通分量：Tarjan 求 SCC
• 割点与桥：删除关键点边后的结构变化
• 二分图判定与匹配：染色判定与匹配入门

6. 高级专题

• 0-1 BFS：权值只有 0/1 时的最短路
• 欧拉路径与回路：每条边恰好走一次
• 网络流与最大流：最大流、最小割、匹配

🧠 看到题目时怎么快速识别

📊 常用算法复杂度

🎯 建议学习顺序

1. 先学 图的表示，理解邻接表和边集数组。
2. 再学 DFS 与 BFS，这是所有图题的底盘。
3. 接着学 单源最短路径，把 BFS、Dijkstra、Bellman-Ford 的边界分清。
4. 然后学 最小生成树 和 拓扑排序。
5. 最后补 强连通分量、二分图、网络流 等专题。

🎯 LeetCode 起步清单

相关主题

• 搜索算法：更通用的搜索框架
• 动态规划：图上 DP、状态压缩
• 贪心算法：Dijkstra、MST 背后都有贪心思想
• 并查集：Kruskal、联通性判断常用

---

返回：算法学习导航