图

图是比树更一般的非线性数据结构,顶点之间是”多对多”的关系,社交网络、地图导航、任务调度、网络拓扑都可以抽象为图。本章围绕图的存储、遍历与四大经典应用展开,是数据结构课程中综合性最强的部分。读完本节,你将能够理解图的基本概念、术语与性质、掌握邻接矩阵与邻接表两种存储结构、掌握广度优先搜索(BFS)与深度优先搜索(DFS)、掌握最小生成树(Prim/Kruskal)与最短路径(Dijkstra/Floyd)算法、理解拓扑排序与关键路径的思想与应用。

本章要解决的问题

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

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

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

章节

发现内容有问题?

告诉我们哪里需要改进。