第一章 图的基本概念与表示 #
1.1 图的定义与分类 #
- 图的基本定义
- 有向图与无向图
- 加权图与无权图
- 连通图与非连通图
- 简单图与多重图
- 完全图与稀疏图
- 二分图与多部图
1.2 图的术语 #
- 顶点与边
- 度、入度与出度
- 路径与回路
- 连通分量
- 子图与生成子图
- 邻接与关联
- 图的同构
1.3 图的存储结构 #
- 邻接矩阵表示法
- 邻接表表示法
- 关联矩阵表示法
- 十字链表表示法
- 邻接多重表表示法
- 边集数组表示法
- 各种存储结构的比较
第二章 图的遍历算法 #
2.1 深度优先搜索 #
- DFS基本思想
- 递归实现
- 非递归实现
- 应用场景
- 时间复杂度分析
- 空间复杂度分析
- 连通分量检测
2.2 广度优先搜索 #
- 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算法
- Reverse-Delete算法
- 次小生成树
- 最小瓶颈生成树
- 斯坦纳树问题
- 欧几里得最小生成树
- 随机生成树
第五章 网络流算法 #
5.1 最大流问题 #
- 流网络定义
- Ford-Fulkerson方法
- Edmonds-Karp算法
- Dinic算法
- 推送-重贴标签算法
- 最大流最小割定理
- 应用实例
5.2 最小割问题 #
- 割的定义
- Stoer-Wagner算法
- 最大流最小割关系
- 全局最小割
- 应用场景
- 算法实现
- 复杂度分析
5.3 匹配与覆盖 #
- 二分图匹配
- 匈牙利算法
- Hopcroft-Karp算法
- 最大权匹配
- 最小顶点覆盖
- 最小边覆盖
- 稳定婚姻问题
第六章 图的连通性问题 #
6.1 连通分量 #
- 强连通分量
- Kosaraju算法
- Tarjan算法
- Gabow算法
- 双连通分量
- 关节点与桥
- 应用实例
6.2 平面图与着色 #
- 平面图判定
- 欧拉公式
- 四色定理
- 图着色算法
- 贪婪着色
- 回溯着色
- 实际应用
6.3 图的分解 #
- 路径分解
- 树分解
- 分支分解
- 团分解
- 独立集分解
- 支配集分解
- 覆盖集分解
第七章 图算法的高级应用 #
7.1 社交网络分析 #
- 中心性度量
- 社区发现
- PageRank算法
- 影响力传播
- 网络演化模型
- 小世界网络
- 无标度网络
7.2 生物信息学应用 #
- 蛋白质相互作用网络
- 基因调控网络
- 代谢网络
- 序列比对图
- 进化树构建
- 通路分析
- 药物靶点预测
7.3 计算机科学应用 #
- 编译器优化
- 程序分析
- 电路设计
- 路由算法
- 调度问题
- 资源分配
- 人工智能应用
第八章 图算法的优化与并行化 #
8.1 算法优化技术 #
- 剪枝策略
- 启发式搜索
- 近似算法
- 随机化算法
- 在线算法
- 增量算法
- 动态图算法
8.2 并行图算法 #
- 并行BFS
- 并行DFS
- 并行最短路径
- 并行连通分量
- MapReduce实现
- GPU加速
- 分布式图计算
8.3 大数据图处理 #
- 图数据库
- 图计算框架
- 图划分策略
- 图压缩技术
- 流图算法
- 子图匹配
- 图挖掘技术