中 进阶
图算法基础#
一句话答案#
图核心算法：BFS/DFS 遍历 O(V+E)、Dijkstra 单源最短路 O(ElogV)、拓扑排序（DAG）、Kruskal 最小生成树。
核心要点
| 算法 | 用途 | 时间 |
|---|---|---|
| BFS | 最短路(无权) | O(V+E) |
| DFS | 连通性/环检测 | O(V+E) |
| Dijkstra | 单源最短路(正权) | O(ElogV) |
| 拓扑排序 | DAG排序 | O(V+E) |
存储： 邻接表(稀疏图) / 邻接矩阵(稠密图)
面试回答（2分钟版）
图算法面试核心是四个：BFS、DFS、Dijkstra和拓扑排序。BFS用队列实现，一层一层往外扩散，天然适合求无权图的最短路径，时间复杂度O(V+E)。DFS用栈或递归，一条路走到底再回头，适合判断连通性和检测环。Dijkstra解决带正权边的单源最短路，核心思想是贪心——每次从未确定的节点中选距离最小的，用优先队列优化后时间O(ElogV)，但注意它不能处理负权边，负权要用Bellman-Ford。拓扑排序只能用在DAG（有向无环图），用入度表+BFS实现，典型应用是课程排课、任务调度。图的存储方面，稀疏图用邻接表省空间，稠密图用邻接矩阵方便查询。
追问与易错
追问方向：
- “BFS 和 DFS 什么场景用哪个？”→ BFS 适合最短路径（无权图）、层序遍历；DFS 适合连通性判断、路径搜索、拓扑排序、强连通分量；空间上 BFS 用队列可能更大，DFS 用栈/递归
- “Dijkstra 能处理负权边吗？”→ 不能，Dijkstra 基于贪心假设「已确定最短路的节点不会再被更新」，负权边会破坏这个假设；负权边用 Bellman-Ford（O(VE)）或 SPFA
- “怎么检测图中的环？”→ 无向图用 DFS 遇到已访问的非父节点即有环，或用并查集判断加边时是否已连通；有向图用 DFS 三色标记法，遇到灰色节点（正在访问）即有环
易错点：
- ❌ DFS 能找最短路——无权图用 BFS 找最短路
- ❌ Dijkstra 是万能最短路——不能处理负权