数据结构课件-第七章.ppt

7.5.1最小生成树 一、相关概念 1、生成树的定义：连通图G的一个子图如果是一棵包含G的所有顶点的树。 2、树的权的定义：生成树各边的权值总和。 3、最小生成树的定义：权最小的生成树，可简记为MST。 举例：图G的顶点表示城市，边表示连接两个城市之间的公路，假设城市之间没有修建任何公路，那么为了把n个城市连接起来，最多可修建n(n-1)/2条公路，最少可修建n-1条公路，则图G的生成树表示了修建公路的可行方案。如果考虑修建造价，那么如何选择n-1条线路，使得修建公路的总造价最小呢？这就是要构造该图的一棵最小生成树。 4、作用 * 普里姆算法的基本思想： 从连通网络 N = { V, E }中的某一顶点 u0 出发,将u0加入到生成树顶点集合U中,选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点v加入到生成树顶点集合U中。 以后每一步从一个顶点u(在 U 中),而另一个顶点v(不在 U 中在V-U中)的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。 采用邻接矩阵作为图的存储表示。 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 例，从顶点A出发，该网络最小生成树的构造过程。  47 52 90 69 54 58 A C G B D E F 55 53 24 42 47 52 54 A C G B D E F 53 24 42 47 54 A G B D E F 53 24 42 54 A B D E F 53 24 42 54 A B D E 53 42 A B 53 A B E 53 42 * PRIM算法分析 普里姆算法实质上就是逐步向U中增加顶点，且使每个被增加的顶点与U中已有的顶点所构成的边具有最小的权值（当存在多条最小权值的边时，可任选其一），直到全部顶点增加完毕为止。 假设网中有n个顶点，普里姆算法的时间复杂度为Ｏ（n２），它与网中边的数目e无关，因此普里姆算法适合于求边稠密的网的最小生成树。 注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一的。 * 2 Kruskal算法 为使生成树上总的权值之和最小，应使每一条边的权值尽可能小，自然从权值最小的边开始选出n-1条权值最小的边为止，但此n-1条边必须不能构成回路。 例Kruskal算法最小生成树构造过程 47 52 90 69 54 58 A C G B D E F 55 53 24 42 A C G B D E F 24 A C G B D E F 24 42 A C G B D E F 24 42 47 A C G B D E F 24 42 47 52 A C G B D E F 24 42 47 53 * 分析： 克鲁斯卡尔算法实质上就是逐步向最小生成树 T中增加权值最小的边，且每增加一条边就将两棵树合并为一棵树，直到增加n-1 条权值最小的边为止。该算法的执行时间取决于图G的边数e 。克鲁斯卡尔算法适合于求边稀疏的网的最小生成树。 7.5.2最短路径 10 一、单源最短路径 1、单源最短路径的定义:在有向网中，从某个源点V0出发 到其它各个顶点的最短路径。 1 2 3 5 4 20 90 50 30 20 40 2、单源最短路径求解方法： 迪杰斯特拉(Dijkstra) 方法 循 环 S W d[2] d[3] d[4] d[5] p[2] p[3] p[4] p[5] 初始化 {1} - 20 ∞ 30 90 1 1 1 1 1 {1,2} 2 20 70 30 90 1 2 1 1 2 {1,2,4} 4 20 40 30 70 1 4 1 4 3 {1,2,4,3} 3 20 40 30 60 1 4 1 3 4 {1,2,4,3,5} 5 20 40 30 60 1 4 1 3 7.5.3拓扑排序  问题的引入： 一项较大的工程往往可以被划分为若干个较小的子工程，把这些子工程称为“活动”(activity)。这些子工程之间通常都存在着一定的制约关系，如某子工程必须在另一些子工程完成之后才能开始等。对于任何一个工程，必须考虑工程安排能否顺利进行？ 这两个方面的问题可以通过有向图的拓扑