山东大学算法导论ppt（老师刘宏）+2019年春季学期考试回忆版。2019年秋季学期考试，偏向于设计算法与证明，更难，都有设计最长路径问题与证明强连通分解，2019年秋还有一题为（一个图的最小生成树，只更改树上一条边的值使之变大，设计算法生成新的最小生成树）。上传主要方便自己看看。

山东大学2018算法导论图论考试复习总结，只考图论部分所以只有图论部分的总结。 本人于考试周吐血总结，包含的内容如下。 算法导论-图论 复习 优质的复习资料 1 基本的图算法 1.1 图的表示 1.2 BFS：广度优先搜索 1.3 DFS：深度优先搜索 1.4 拓扑排序 1.5 强连通分量 2 最小生成树 2.1 最小生成树的形成 2.2 Kruskal算法和Prim算法 3 单源最短路径 3.1 Bellman-Ford算法 3.2 有向无环图（DAG图）中单源最短路径问题 3.3 Dijkstra算法 3.4 差分约束和最短路径 3.5 最短路径的性质证明（三上无路收钱） 4 所有结点对的最短路径问题 4.1 矩阵乘法 matrix multiplication improved matrix mult. 4.2 Floyd-Warshall算法 4.3 用于稀疏图的Johnson算法 5 最大流 5.1 流网络 5.2 Ford-Fulkerson方法 5.3 最大二分匹配 习题 附录 Table of running times

实验5.生成一个100个点，300条边的无向图，对于图中的每个连通分支，计算其中的割点。从连通分支中删除该点，会导致分支不再连通的点被称为割点。 实验6.用局部搜索算法，求一个无向图的最小生成树。生成一个无向连通图，有100个点，1000条边，边上的权重是1到20之间的随机整数。用Kruskal或prim算法求得该图的最小生成树，验证局部搜索算法的对错。 实验7.已知Bellman-Ford算法能判断一个有向加权图是否含有负权重的圈。请设计一个算法，从图中找出一个负圈。图：100个点，500条边，每条边的权重是[-5,5]之间的随机非零整数。要求多次生成这样的随即图，直到发现负圈为止。