第一章 图论基础 #

1.1 图的基本概念 #

• 图的定义与分类
• 顶点、边、权重的概念
• 有向图与无向图
• 简单图与多重图
• 图的表示方法：邻接矩阵、邻接表

1.2 图的遍历算法 #

• 深度优先搜索（DFS）
• 广度优先搜索（BFS）
• 遍历算法的应用场景
• 遍历的时间复杂度分析

第二章 连通性概念 #

2.1 无向图连通性 #

• 连通图与连通分量
• 连通性的判定条件
• 割点与桥
• 双连通分量

2.2 有向图连通性 #

• 强连通分量
• 弱连通分量
• Kosaraju算法
• Tarjan算法

第三章 连通性算法 #

3.1 最小生成树算法 #

• Kruskal算法原理与实现
• Prim算法原理与实现
• 最小生成树的应用
• 算法复杂度比较

3.2 最短路径算法 #

• Dijkstra算法
• Bellman-Ford算法
• Floyd-Warshall算法
• 最短路径的应用场景

3.3 网络流算法 #

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

第四章 高级连通性问题 #

4.1 平面图连通性 #

• 平面图的定义与性质
• 欧拉公式
• 平面图的连通性判定
• 平面图的可平面性测试

4.2 动态连通性 #

• 并查集数据结构
• 动态连通性问题
• 路径压缩与按秩合并
• 在线算法与离线算法

第五章 实际应用 #

5.1 社交网络分析 #

• 社区发现算法
• 影响力传播模型
• 网络中心性度量
• 小世界现象

5.2 计算机网络 #

• 网络拓扑结构
• 路由算法
• 网络可靠性分析
• 容错机制设计

5.3 生物信息学 #

• 蛋白质相互作用网络
• 基因调控网络
• 代谢通路分析
• 系统生物学应用

第六章 算法优化与扩展 #

6.1 并行连通性算法 #

• 并行BFS算法
• 并行连通分量算法
• MapReduce实现
• GPU加速算法

6.2 近似算法 #

• 连通性近似算法
• 随机化算法
• 近似比分析
• 实际应用中的权衡

6.3 大数据场景下的连通性 #

• 流式图算法
• 图数据库中的连通性查询
• 分布式图计算框架
• 增量式连通性维护