本资料为山东大学2018年《算法导论》课程中图论部分的复习要点总结，涵盖关键概念、重要算法及典型例题解析，旨在帮助学生巩固知识结构，掌握考试重点。
山东大学2018年《算法导论》图论考试复习总结仅涵盖图论部分的内容。以下是本人在考试周期间整理的高质量复习资料：
**算法导论-图论**
**一、基本的图算法**
1. **图的表示**
2. **BFS：广度优先搜索**
3. **DFS：深度优先搜索**
4. **拓扑排序**
5. **强连通分量**
**二、最小生成树**
1. 最小生成树的概念
2. Kruskal算法和Prim算法
**三、单源最短路径问题**
1. Bellman-Ford算法
2. 有向无环图（DAG）中的单源最短路径问题
3. Dijkstra算法
4. 差分约束与最短路径
5. 最短路径的性质证明
**四、所有结点对之间的最短路径**
1. 矩阵乘法及其优化版本改进矩阵乘法算法（Improved Matrix Multiplication）
2. Floyd-Warshall算法
3. 用于稀疏图的Johnson算法
**五、最大流问题**
1. 流网络的概念
2. Ford-Fulkerson方法
3. 最大二分匹配
附录：运行时间表
5星
