{< katex />}
第一章 图的基本概念与表示方法 #
1.1 图的基本定义 #
- 图的定义与组成要素
- 有向图与无向图
- 简单图与多重图
- 完全图与补图
- 子图与生成子图
1.2 图的表示方法 #
- 邻接矩阵表示法
- 邻接表表示法
- 关联矩阵表示法
- 边集表示法
- 不同表示方法的比较与选择
1.3 图的基本性质 #
- 度与握手定理
- 路径与回路
- 连通性与连通分量
- 图的同构
- 平面图与欧拉公式
第二章 图的遍历算法 #
2.1 深度优先搜索 #
- DFS基本原理与实现
- 递归与非递归实现
- DFS树与DFS森林
- 时间戳与颜色标记
- 应用场景与复杂度分析
2.2 广度优先搜索 #
- BFS基本原理与实现
- 队列的使用与层次遍历
- BFS树与最短路径
- 双向BFS算法
- 应用场景与复杂度分析
2.3 遍历算法的应用 #
- 连通分量检测
- 二分图判定
- 拓扑排序
- 强连通分量
- 环路检测
第三章 最短路径算法 #
3.1 单源最短路径 #
- Dijkstra算法原理
- 优先队列优化
- 负权边处理限制
- Bellman-Ford算法
- SPFA算法及其优化
3.2 所有节点对最短路径 #
- Floyd-Warshall算法
- 动态规划思想
- 路径重建方法
- Johnson算法
- 不同算法的比较
3.3 特殊图的最短路径 #
- 无权图的最短路径
- 有向无环图的最短路径
- 网格图的最短路径
- 含负权环的检测
- 实际应用案例分析
第四章 最小生成树算法 #
4.1 Prim算法 #
- 算法原理与步骤
- 不同实现方式比较
- 优先队列优化
- 时间复杂度分析
- 应用实例
4.2 Kruskal算法 #
- 算法原理与步骤
- 并查集数据结构
- 边排序策略
- 时间复杂度分析
- 应用实例
4.3 其他生成树算法 #
- Borůvka算法
- 反向删除算法
- 次小生成树
- 最小瓶颈生成树
- 生成树计数问题
第五章 网络流算法 #
5.1 最大流问题 #
- 流网络基本概念
- Ford-Fulkerson方法
- Edmonds-Karp算法
- Dinic算法
- 推送-重贴标签算法
5.2 最小割问题 #
- 最大流最小割定理
- Stoer-Wagner算法
- 割的应用场景
- 全局最小割
- 近似算法
5.3 特殊网络流问题 #
- 二分图匹配
- 多重源汇问题
- 带上下界的流
- 费用流问题
- 实际应用案例
第六章 图的匹配与覆盖 #
6.1 匹配算法 #
- 二分图最大匹配
- 匈牙利算法
- Hopcroft-Karp算法
- 一般图匹配
- 带权匹配
6.2 覆盖算法 #
- 点覆盖与边覆盖
- 最小点覆盖
- 最小边覆盖
- 支配集问题
- 独立集问题
6.3 匹配与覆盖的关系 #
- Kőnig定理
- 匹配覆盖对偶性
- 应用实例分析
- 近似算法
- 在线算法
第七章 图的连通性算法 #
7.1 连通分量 #
- 强连通分量
- Kosaraju算法
- Tarjan算法
- Gabow算法
- 双连通分量
7.2 割点与桥 #
- 割点检测算法
- 桥检测算法
- 低链接值计算
- 应用场景分析
- 动态连通性
7.3 连通度计算 #
- 点连通度
- 边连通度
- Menger定理
- 流方法计算连通度
- 近似算法
第八章 平面图与着色算法 #
8.1 平面图算法 #
- 平面性检测
- 平面嵌入算法
- 对偶图构造
- 外平面图
- 网格嵌入
8.2 图着色算法 #
- 顶点着色问题
- 边着色问题
- 贪心着色算法
- 回溯着色算法
- 着色数的界
8.3 特殊图的着色 #
- 二分图着色
- 平面图着色
- 完美图着色
- 区间图着色
- 实际应用案例
第九章 高级图算法 #
9.1 随机化算法 #
- 随机游走
- 随机割算法
- 概率方法
- 拉斯维加斯算法
- 蒙特卡洛算法
9.2 并行图算法 #
- 并行BFS
- 并行连通分量
- 并行最短路径
- MapReduce图算法
- GPU加速图算法
9.3 近似算法 #
- 旅行商问题近似
- 斯坦纳树近似
- 顶点覆盖近似
- 性能保证分析
- 不可近似性结果
第十章 图算法应用与实践 #
10.1 实际应用领域 #
- 社交网络分析
- 路由算法
- 调度问题
- 生物信息学
- 计算机视觉
10.2 算法工程实践 #
- 图数据库应用
- 大规模图处理
- 内存优化技巧
- 缓存友好实现
- 性能调优方法
10.3 新兴研究方向 #
- 动态图算法
- 流图算法
- 量子图算法
- 机器学习与图算法
- 未来发展趋势