数据分析与算法设计7-图最小生成树、最短路径

1、数据分析与算法设计7：图（最小生成树、最短路径）信电学院 王梁昊 副研究员(645840)浙江大学玉泉校区信电楼505室主要内容最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图传递闭包Warshall算法（动态规划，8.4.1）完全最短路径Floyd算法（动态规划，8.4.2）主要内容最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图传递闭包Warshall算法（动态规划，

2、8.4.1）完全最短路径Floyd算法（动态规划，8.4.2）最小生成树最小生成树（minimum spanning tree）Prim算法Prim算法Prim算法Prim算法的正确性证明归纳法反证法Prim算法的效率取决于表示图的数据结构、表示V-VT的优先队列的数据结构图：权重矩阵优先队列：无序数组运行时间属于 (|V|2)图：邻接链表优先队列：最小堆运行时间属于 (|V|-1+|E|)O(log|V|)O(|E|log|V|)P.22主要内容最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图

3、传递闭包Warshall算法（动态规划，8.4.1）完全最短路径Floyd算法（动态规划，8.4.2）Kruskal算法Kruskal算法Kruskal算法看上去似乎很简单，复杂度似乎低于Prim算法但每次迭代时，必须要检查新边加入后是否会形成回路Kruskal算法换一个角度解释Kruskal算法（从森林的角度）：初始时，有|V|个树构成的森林；最终的森林由单独的树构成；每次迭代中新边的加入等价于从图中找到一条边，当顶点分别属于不同的树时，选取该边，使两棵树变为一棵更大的树。两个顶点是否属于同棵树？union-find(并查)算法不相交子集和并查算法不相交子集和并查算法实现这种数据结构的两种做

4、法快速查找（quick find）其查找操作的时间效率是最优的快速求并（quick union）其求并集操作的时间效率是最优的快速查找（quick find）makeset(x)(1) - (n)find(x)(1)union(x)(n2)？ O(nlogn)快速求并（quick union）(1) - (n)makeset(x)find(x)(n)?O(logn)union(x)(1)主要内容最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图传递闭包Warshall算法（动态规划，8.4.1）完

5、全最短路径Floyd算法（动态规划，8.4.2）单源最短路径问题单源最短路径问题（single-source shortest- paths problem） 求源到所有其他顶点之间的一系列最短路径 注意：不是从一个起点出发访问所有其他顶点的单条最短路径（旅行商问题）Dijkstra算法不含负权重的图Dijkstra算法主要内容最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图传递闭包Warshall算法（动态规划，8.4.1）完全最短路径Floyd算法（动态规划，8.4.2）有向图的传递闭包深度

6、优先查找/广度优先查找Warshall算法Warshall算法通过一系列n阶布尔矩阵来构造传递闭包路径的每个中间顶点的编号不大于k任何中的元素都可以通过计算得到Warshall算法主要内容最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图传递闭包Warshall算法（动态规划，8.4.1）完全最短路径Floyd算法（动态规划，8.4.2）完全最短路径（all-pairs shortestpaths）完全最短路径问题加权连通图（无向或有向）找到从每个顶点到其他所有顶点之间的距离（最短路径的长度）距离矩阵（distance matrix）Floyd算法个通过一系列n阶矩阵计算距离矩阵路径的每个中间顶点的编号不大于k每一中的任何元素可以通过计算得到Floyd算法内容回顾最小生成树Prim算法（贪婪技术，9.1）最小生成树Kruskal算法（贪婪技术，9.2）单源最短路径Dijkstra算法（贪婪技术，9.3）有向图传递闭包Warshall算法（动态规划，8.4.1）完全最短路径Floyd算法（动态规划，8.4.2）Prim算法Kruska