01

60 秒回答模板

图论算法可以按问题分：遍历和连通性用 DFS/BFS、并查集；无权最短路用 BFS，非负权单源最短路用 Dijkstra，允许负权用 Bellman-Ford，全源最短路可用 Floyd；最小生成树用 Kruskal 或 Prim；DAG 依赖用拓扑排序；强连通分量用 Tarjan/Kosaraju；二分图匹配和网络流处理匹配、容量和最大流问题。回答时要先说明图是有向还是无向、是否有权、是否有负权、稀疏还是稠密，再选算法和复杂度。

考点 核心机制与工程取舍
难度 中高频面试题
回答目标 按定义、机制、场景讲清楚
02

深入解析

01

图表示影响复杂度

邻接表适合稀疏图，DFS/BFS 是 `O(V + E)`；邻接矩阵适合稠密图或快速判断两点是否有边，但空间是 `O(V²)`；Kruskal 常用边集排序。

02

遍历和连通性是一类

DFS/BFS 可解决连通块、层级遍历、环检测、无权最短路。动态连通性或合并集合常用并查集，并用路径压缩和按秩合并降低复杂度。

03

最短路要看权重条件

无权图 BFS；边权非负用 Dijkstra，堆优化常见复杂度是 `O(E log V)`；有负权边考虑 Bellman-Ford；全源最短路且点数不大时可用 Floyd。

04

生成树和依赖排序不是一回事

最小生成树面向无向连通带权图，目标是选边连通所有点且总权重最小，常用 Kruskal/Prim；拓扑排序处理有向无环依赖，可判断是否有环。

05

高阶问题要说出适用场景

强连通分量处理有向图互相可达；二分图匹配解决任务分配；网络流处理容量约束和最大流最小割。回答到这里能体现分类而非死记。

03

易错点

  • 只背算法名，不说明图类型和适用条件。
  • 把 BFS、Dijkstra、Floyd 的使用边界混在一起。
  • 不区分最短路和最小生成树的目标。
  • 完全不提复杂度和图表示，无法根据数据规模选算法。
04

面试官追问

Dijkstra 为什么不能处理负权边？

它每次确定当前最短点后不再回头，负权边可能让已确定的距离变小，破坏贪心前提。

Prim 和 Kruskal 怎么选？

Kruskal 按边排序并用并查集跳过环，适合边集清晰的稀疏图；Prim 从点扩展，配合堆也适合稀疏图，矩阵实现更适合稠密图。

拓扑排序能解决什么问题？

处理 DAG 依赖顺序，例如课程安排、编译依赖、任务调度。若最终无法输出所有点，说明有环。

无权图两点最短路为什么用 BFS？

BFS 按层扩展，第一次到达某个点时经过的边数最少，这个前提依赖每条边权相同。