图
6.1 图的定义和基本术语
6.1.1 图的定义
6.1.2 图的基本术语
1. 子图
2. 无向完全图和有向完全图
3. 稀疏图和稠密图
4. 权和网
5. 邻接点
6. 度、入度和出度
7. 路径和路径长度
8. 回路或环
9. 简单路径、简单回路或简单环
10. 连通、连通图和连通分量
11. 强连通图和强连通分量
12. 连通图的生成树
13. 有向树和生成森林
6.2 案例引入
6.3 图的类型定义
6.4 图的存储结构
6.4.1 邻接矩阵
1. 邻接矩阵表示法
2. 采用邻接矩阵表示法创建无向网
3. 邻接矩阵表示法的优缺点
6.4.2 邻接表
1. 邻接表表示法
（1）表头节点表
（2）边表
2. 采用邻接表表示法创建无向图
3. 邻接表表示法的优缺点
6.4.3 十字链表
6.4.4 邻接多重表
6.5 图的遍历
6.5.1 深度优先搜索
1. 深度优先搜索遍历的过程
2. 深度优先搜索遍历的算法实现
3. 深度优先搜索遍历的算法分析
6.5.2 广度优先搜索
1. 广度优先搜索遍历的过程
2. 广度优先搜索遍历的算法实现
3. 广度优先搜索遍历的算法分析
6.6 图的应用
6.6.1 最小生成树
1. 普里姆算法
（1）普里姆算法的构造过程
（2）普里姆算法的实现
2. 克鲁斯卡尔算法
（1）克鲁斯卡尔算法的构造过程
（2）克鲁斯卡尔算法的实现
6.6.2 最短路径
1. 从某个远点到其余各顶点的最短路径
就是当时学的单源最短路径算法
（1）迪杰斯特拉算法的求解过程
（2）迪杰斯特拉算法的实现
2. 每一对顶点之间的最短路径
弗洛伊德算法
6.6.3 拓扑排序
1. AOV– 网
2. 拓扑排序的过程
3. 拓扑排序的实现
6.6.4 关键路径
1. AOV– 网
（1）事件 $v_i$ 的最早发生时间 $ve(i)$
（2）事件 $v_i$ 的最迟发生时间 $vl(i)$
（3）活动 $a_i\ =\ < v_j,v_k >$ 的最早开始时间 $e(i)$
（3）活动 $a_i\ =\ < v_j,v_k >$ 的最晚开始时间 $l(i)$
2. 关键路径求解的过程
（1）对途中定点进行排序，在排序过程中按拓扑序列求出每个时间的最早发生时间 $ve(i)$
（2）按逆拓扑序列求出每个事件的最迟发生时间 $v(i)$
（3）求出每个活动 $a_i$ 的最早开始时间 $e(i)$
（4）求出每个活动 $a_i$ 的最晚开始时间 $l(i)$
（5）找出 $e(i)=l(i)$ 的活动 $a_i$，即关键活动
由关键活动形成的由源点到汇点的每一条路径就是关键路径，关键路径有可能不止一条
3. 关键路径算法的时实现
6.7 案例分析与实现
6.8 LeetCode 算法练习题
6.9 小结