图的存储方式与典型应用
哪些公司问过
答案要点
- 邻接矩阵:O(n²) 空间,判边 O(1),适合稠密图
- 邻接表:O(V+E) 空间,适合稀疏图,最常用
- 边集数组:存所有边,适合 Kruskal;链式前向星:邻接表的数组实现
- 应用:社交网络、地图导航最短路径、拓扑排序(任务依赖)、网络路由、推荐系统
- 算法:BFS、DFS、Dijkstra(不含负权)、最小生成树、拓扑排序
易错点
- 稀疏图用邻接矩阵,浪费空间
- Dijkstra 用于有负权边的图
- 把有向图和无向图的邻接表存储混淆
- BFS 没有标记已访问节点,造成重复入队
面试官常见追问
- Dijkstra 算法的原理和步骤是什么?
- Dijkstra 为什么不能处理负权边?
- BFS 和 DFS 有什么区别和应用?
- 如何判断图中有没有环?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。