图 BFS DFS 并查集

1. 一句话总结

图描述多对多关系，BFS 按层扩展，DFS 深度搜索，并查集快速判断连通性。

2. 通俗解释

树像上下级，图像城市道路。BFS 一圈圈扩散，DFS 沿路走到底，并查集把属于同一团体的人合并到同一个代表名下。

3. 核心概念

• 邻接矩阵：二维数组表示边，查边快但空间 O(n²)。
• 邻接表：每个点存相邻点，适合稀疏图。
• BFS：队列按层遍历。
• DFS：递归或栈深入搜索。
• 并查集：find/union 维护连通性。
• 拓扑排序：有向无环图依赖顺序。

4. 底层原理

• BFS 第一次到达目标时步数最少，适合无权最短路。
• DFS 通过递归栈保存路径，适合连通块、回溯、环检测。
• 图遍历必须 visited，否则有环会死循环。
• 并查集路径压缩加按秩合并后近似 O(1)。
• 拓扑排序可用入度为 0 的节点逐步删除。

5. 面试标准回答

图用于表示多对多关系，常用邻接矩阵和邻接表。邻接矩阵查边快但空间大，适合稠密图；邻接表更省空间，适合稀疏图。BFS 用队列按层扩展，常用于无权图最短路径；DFS 用递归或栈深入，常用于连通块、路径枚举、环检测。并查集不关心具体路径，只维护两个节点是否属于同一集合，适合连通性判断。图题一定要处理 visited，避免重复访问或死循环。

6. 高频追问

追问 1：图 BFS DFS 并查集面试第一句话怎么答？

先给结论：邻接矩阵：二维数组表示边，查边快但空间 O(n²)。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

BFS 第一次到达目标时步数最少，适合无权最短路。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：DFS 通过递归栈保存路径，适合连通块、回溯、环检测。

追问 5：实际开发中怎么体现？

社交关系、推荐系统可建模为图。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 社交关系、推荐系统可建模为图。
• 并查集可用于账号合并、网络连通性。
• 拓扑排序常用于课程表和任务编排。

9. 背诵速记

图是多对多关系。邻接矩阵查边快但占空间，邻接表适合稀疏图。BFS 用队列按层走，DFS 用递归或栈深入，并查集用 find/union 判断连通性。