图

内容

• 图的定义；
• 图的实现（包括邻接矩阵和邻接表）和基本操作；
• 图的两种遍历；
• 图的基本应用，包括最小支撑树、最短路径、拓扑排序和关键路径。

要求

• 掌握图的定义，包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点；
• 掌握图采用邻接矩阵和邻接表进行存储的差异性；
• 掌握广度优先遍历和深度优先遍历；
• 掌握最小支撑树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法、BellmanFord算法、Floyd算法）、拓扑排序以及关键路径的实现过程。