第一部分 图论基础 #

图的基本概念 #

• 图的定义与分类
• 顶点、边与权值
• 有向图与无向图
• 连通性与路径
• 图的表示方法

图的基本算法 #

• 深度优先搜索(DFS)
• 广度优先搜索(BFS)
• 拓扑排序
• 图的遍历复杂度分析

第二部分 最短路径算法 #

单源最短路径 #

• Dijkstra算法原理与实现
• Bellman-Ford算法
• SPFA算法优化
• 负权边处理策略

多源最短路径 #

• Floyd-Warshall算法
• Johnson算法
• 最短路径应用场景

第三部分 最小生成树 #

经典最小生成树算法 #

• Prim算法详解
• Kruskal算法详解
• 并查集数据结构
• 最小生成树性质证明

进阶生成树问题 #

• 次小生成树
• 最小瓶颈生成树
• 生成树计数问题

第四部分 网络流算法 #

最大流问题 #

• Ford-Fulkerson方法
• Edmonds-Karp算法
• Dinic算法优化
• 最大流最小割定理

最小费用流 #

• 最小费用最大流
• 费用流算法实现
• 网络流建模技巧

第五部分 匹配与覆盖 #

二分图匹配 #

• 匈牙利算法
• Hopcroft-Karp算法
• 二分图性质与应用

集合覆盖问题 #

• 顶点覆盖
• 边覆盖
• 支配集问题

第六部分 强连通分量 #

连通性分析 #

• Kosaraju算法
• Tarjan算法
• 强连通分量应用

双连通分量 #

• 割点与桥
• 双连通分量分解
• 连通性保持算法

第七部分 平面图与着色 #

平面图理论 #

• 平面图判定
• 欧拉公式
• 对偶图概念

图着色问题 #

• 顶点着色
• 边着色
• 四色定理简介

第八部分 高级图算法 #

近似算法 #

• 旅行商问题近似解
• 斯坦纳树问题
• 近似比分析

随机化算法 #

• 随机游走算法
• 概率方法在图论中的应用

第九部分 实际应用 #

社交网络分析 #

• 社区发现算法
• 影响力最大化
• 图神经网络简介

路径规划与导航 #

• A*搜索算法
• 实时路径规划
• 多目标路径优化

第十部分 算法优化与扩展 #

并行图算法 #

• 图计算的并行化
• 分布式图处理框架

动态图算法 #

• 增量图算法
• 动态图维护技术
• 在线图算法设计