图 高频追问 Q&A

图 高频追问 Q&A

1. Q: 邻接表和邻接矩阵怎么选？

A: 稀疏图用邻接表更省空间，稠密图用邻接矩阵查询边更快。（深入阅读：图基础知识速览）

2. Q: DFS 和 BFS 最核心差异？

A: DFS 偏深度探索，BFS 按层推进，BFS 常用于无权最短路径。（深入阅读：深度优先搜索基础知识速览、广度优先搜索基础知识速览）

3. Q: 拓扑排序适用于什么图？

A: 仅适用于有向无环图（DAG）。（深入阅读：拓扑排序：课程表问题）

4. Q: 如何判断图是否有环？

A: 有向图可用拓扑排序计数；无向图可用并查集或 DFS 回边判断。（深入阅读：拓扑排序：课程表问题、图的连通性与 DFS 遍历）

5. Q: 面试写图题先做什么？

A: 先定建图方式，再确认遍历策略（DFS/BFS/并查集/最短路）。（深入阅读：图基础知识速览）