树与图的生成树精要.ppt

第3章 树与图的生成树 例1 下图所示的网络代表6个城市间的交通网，边上权是公路的造价，现在要用公路把6个城市联系起来，这要修筑5条公路，如何设计使得这5条公路总的造价最小。 1 生成树 生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。 用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 生成树是连通图的最小连通子图。所谓最小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。 最小生成树(MST, Minimum Spannirng Tree) 最小生成树：生成树各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。 构造最小生成树的准则： 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点； 不能使用产生回路的边。 构造最小生成树的方法：克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。都得遵守以上准则。 2 克鲁斯卡尔算法 先看例子。 克鲁斯卡尔算法的基本思想(以边为主导地位：始终都是选择当前可用的最小权值边)： 设有一个有 n 个顶点的连通网络 N = { V, E }，最初先构造一个只有 n 个顶点，没有边的非连通图 T = { V, ? }, 图中每个顶点自成一个连通分量。 当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。 如此重复下去，直到所有顶点在同一个连通分量上为止。 用克鲁斯卡尔算法构造最小生成树的过程 本算法思想 先在二维数组AdjUnion里查找到权值最小的边（标志位为1和-1的不予考虑） 检查这条边的2个顶点i和j是不是在同一个连通分量上（在一维数组VerUnion里通过判断这条边的2个顶点为下标的元素值是否相同），如果在同一个连同分量上，则舍去（在AdjUnion将这条边的标志置为-1），如果不在的话，执行下列操作： 输出这条边; 将标志位置为1; 在VerUnion数组中将以顶点j所在的连通分量的每个顶点为下标的元素值设为VerUnion[i]; 重复执行1、2步，直至最小生成树中的边数为VerNum-1 算法分析 整个算法的时间复杂性是O(n2) 3 普里姆算法 先看例子。 普里姆算法的基本思想(以顶点为主导地位：从起始顶点出发，通过选择当前可用的最小权值边把顶点加入到生成树当中来) ： 从连通网络 N = { V, E }中的某一顶点 u0出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。 以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 Prim算法的优化 lowcost数组和nearvex数组是不是可以合二为一？(见ZOJ1586的解题报告) MST例子 ZOJ 1203 ZOJ 1406 解题报告！ ZOJ 1586 问题： 对于一个给定的无向连通图，它的MST是唯一的吗？ 答案：MST权值总和是唯一的，但有可能可以选择不同的边。 POJ 1679 The Unique MST 第2届校内赛：Problem A: Another MST? * 信息学院信息技术教研室 Vt V2 V4 V3 V1 2 4 8 4 2 7 9 1 4 6 V1 V8 V9 V10 V7 V4 V3 V6 V5 V2 图论算法理论、 实现及应用 王桂平 1 5 6 2 4 3 16 19 21 23 18 14 11 6 5 6 克鲁斯卡尔算法的基本思想 T = (V, φ)； While ( T中所含边数 n-1 ) { 从E中选取当前最短边u,v; 从E中删除边u,v; if (u,v 并入T之后不产生回路 ) 将边 u,v 并入T中； } 0 5 6 2 3 4 28 1 10 25 24 22 18 12 16 14 0 5 6 2 3 4 1 10 25 22 12 16 14 在Kruskal算法里要用到最小堆(MinHeap)和并查集(DisjointSets)。 最小堆：用来存放E中所有的边。 并查集：用来检查依附于1条边的2个顶点是否在同一个连同分量上。 为简化起见，本算法中不使用最小堆和并查集，分别使用一维数组和二维数组来替代并查集和最小堆，并且可以很好地体现算法的思想。 一维数组VerUnion[VerNum]：顶点信息 其中的元素值相同的话，表示在同一个连通分量上