图

图是比树更一般的非线性数据结构，顶点之间是”多对多”的关系，社交网络、地图导航、任务调度、网络拓扑都可以抽象为图。本章围绕图的存储、遍历与四大经典应用展开，是数据结构课程中综合性最强的部分。

本章要解决的问题

如何表示顶点之间任意复杂的连接关系？邻接矩阵与邻接表是两种最基础的存储方式，各有权衡。在此基础上，如何用 BFS/DFS 遍历图，如何用 Prim/Kruskal 求最小生成树、用 Dijkstra/Floyd 求最短路径，如何做拓扑排序与关键路径分析，是本章需要逐一掌握的核心问题。

学习目标

• 理解图的基本概念、术语与性质
• 掌握邻接矩阵与邻接表两种存储结构
• 掌握广度优先搜索（BFS）与深度优先搜索（DFS）
• 掌握最小生成树（Prim/Kruskal）与最短路径（Dijkstra/Floyd）算法
• 理解拓扑排序与关键路径的思想与应用

章节导航

建议阅读顺序

基础路线：基本概念 → 存储结构 → 图的遍历，先掌握图的表示与两种搜索。

进阶路线：基本应用 → 总结，理解最小生成树、最短路径、拓扑排序等经典算法。