2023年梳理图论部分的数据结构详解——第四章详细解读

4.1 图的基本概念

4.2 图的存储及基本操作

4.3 图的遍历

• 深度优先搜索 DFS（类似树的先根遍历）
• 广度优先搜索 BFS（树的广度优先遍历）

树的深度优先遍历

4.4 图的基本应用

最小生成树（最小代价树）

• 普里姆算法（每次选择一个顶点）
  从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
  同一个图可能会有多个最小生成树。但最小代价相同。

• 克鲁斯卡尔算法（每次选择一条边）
  每次选择一条权值最小的边，使这两条边的两头连通（原本已经联通就不选），直到所有节点都连通。

• 图的广度优先搜索算法

最短路径

从某顶点到其余各顶点的最短路径
【题目】

拓扑排序

关键路径