山东大学2018年算法导论及图论考试复习总结。

简介：
山东大学2018年算法导论图论考试复习总结，由于考试仅针对图论部分，因此这份总结仅涵盖了图论相关的知识点，是本人在考试周期间精心整理和归纳的结果。其中包含的详细内容如下：首先，对算法导论中的图论部分进行了系统性的复习，并提供了优质的复习资料。具体包括：对基本图算法的阐述，涵盖了图的表示方法、广度优先搜索（BFS）、深度优先搜索（DFS）、拓扑排序以及强连通分量等核心概念。随后，深入探讨了最小生成树算法，包括最小生成树的构建方法、Kruskal算法和Prim算法的详细解析。接着，详细讲解了单源最短路径算法，涵盖了Bellman-Ford算法、有向无环图（DAG）中单源最短路径问题、Dijkstra算法以及差分约束和最短路径性质证明。最后，对所有结点对的最短路径问题进行了分析，包括矩阵乘法优化后的矩阵乘法、Floyd-Warshall算法以及用于稀疏图的Johnson算法。此外，还涉及最大流的相关内容，包括流网络模型、Ford-Fulkerson方法以及最大二分匹配等。附录中包含了各类算法的运行时间表。