《【课件】第3章 树与图的生成树》由会员分享，可在线阅读，更多相关《【课件】第3章 树与图的生成树（28页珍藏版）》请在金锄头文库上搜索。
1、第3章树与图的生成树 例1 下图所示的网络代表6个城市间的交通网 边上权是公路的造价 现在要用公路把6个城市联系起来 这要修筑5条公路 如何设计使得这5条公路总的造价最小 1生成树 生成树 连通图G的一个子图如果是一棵包含G的所有顶点的树 则该子图称为G的生成树 用不同的遍历图的方法 可以得到不同的生成树 从不同的顶点出发 也可能得到不同的生成树 生成树是连通图的最小连通子图 所谓最小是指 若在树中任意增加一条边 则将出现一个回路 若去掉一条边 将会使之变成非连通图 按照生成树的定义 n个顶点的连通网络的生成树有n个顶点 n 1条边 最小生成树 MST MinimumSpannirngTree
2、 最小生成树 生成树各边的权值总和称为生成树的权 权最小的生成树称为最小生成树 构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树 必须使用且仅使用n 1条边来联结网络中的n个顶点 不能使用产生回路的边 构造最小生成树的方法 克鲁斯卡尔 Kruskal 算法和普里姆 Prim 算法 都得遵守以上准则 2克鲁斯卡尔算法 先看例子 克鲁斯卡尔算法的基本思想 以边为主导地位 始终都是选择当前可用的最小权值边 设有一个有n个顶点的连通网络N V E 最初先构造一个只有n个顶点 没有边的非连通图T V 图中每个顶点自成一个连通分量 当在E中选到一条具有最小权值的边时 若该边的两个顶点落在不同的
3、连通分量上 则将此边加入到T中 否则将此边舍去 重新选择一条权值最小的边 如此重复下去 直到所有顶点在同一个连通分量上为止 克鲁斯卡尔算法的基本思想T V While T中所含边数 从E中删除边 if 并入T之后不产生回路 将边并入T中 用克鲁斯卡尔算法构造最小生成树的过程 在Kruskal算法里要用到最小堆 MinHeap 和并查集 DisjointSets 最小堆 用来存放E中所有的边 并查集 用来检查依附于1条边的2个顶点是否在同一个连同分量上 为简化起见 本算法中不使用最小堆和并查集 分别使用一维数组和二维数组来替代并查集和最小堆 并且可以很好地体现算法的思想 一维数组VerUnion
4、 VerNum 顶点信息其中的元素值相同的话 表示在同一个连通分量上 初始时 每个元素的值为其下标 即每个顶点自成一个连通分量 在最小生成树产生过程中 如果查找到的权值最小的边的两个顶点在同一个连通分量 元素值相同 则要舍去这条边 如果不在同一个连同分量上 则要把这条边加进来 并把对应的元素值设为相同 二维数组AdjUnion AdjNum 4 边的信息二维数组中的每个元素的4个分量分别为标志F 每条边的起点i 终点j 权值w 标志位初始值为0 表示边没有加入到生成树中 初始时边的集合为空集 标志位的修改 当查找到权值最小的边 并且这条边的2个顶点不在同一个连通分量上 则修改对应的标志位为1
5、如果在同一个连通分量上 则这条边要舍去 对应的标志位设为 1 本算法思想 先在二维数组AdjUnion里查找到权值最小的边 标志位为1和 1的不予考虑 检查这条边的2个顶点i和j是不是在同一个连通分量上 在一维数组VerUnion里通过判断这条边的2个顶点为下标的元素值是否相同 如果在同一个连同分量上 则舍去 在AdjUnion将这条边的标志置为 1 如果不在的话 执行下列操作 输出这条边 将标志位置为1 在VerUnion数组中将以顶点j所在的连通分量的每个顶点为下标的元素值设为VerUnion i 重复执行1 2步 直至最小生成树中的边数为VerNum 1 AdjUnion VerUnio
6、n defineMAX VER NUM10 顶点个数最大值 defineMAX10000intVerNum 顶点个数intAdjNum 边的个数intEdge MAX VER NUM MAX VER NUM 图的邻接矩阵voidKruskal 假设图的邻接矩阵 顶点个数 边的个数这些信息已经读进来了 int VerUnion newint VerNum int AdjUnion 4 newint AdjNum 4 for inti 0 i VerNum i VerUnion i i 构造顶点数组 值相同表示在同一个连通分量上intj 0 k 0 for i 0 i VerNum 1 i 构造边
7、的数组 for j i 1 j VerNum j if G AdjMatrix i j MAX 0 边还未检测过 1 边已经加进来了 1 检测过但因为在同一个连通分量上 被舍去了AdjUnion k 0 0 AdjUnion k 1 i AdjUnion k 2 j AdjUnion k 3 G AdjMatrix i j k j 0 intcount 0 while count VerNum 1 intmin MAX for k 0 k AdjNum k 找到权值最小的边AdjUnion j if AdjUnion k 0 0 如果是 舍去 重来 1 2 算法分析 整个算法的时间复杂性是O
8、n2 3普里姆算法 先看例子 普里姆算法的基本思想 以顶点为主导地位 从起始顶点出发 通过选择当前可用的最小权值边把顶点加入到生成树当中来 从连通网络N V E 中的某一顶点u0出发 选择与它关联的具有最小权值的边 u0 v 将其顶点加入到生成树的顶点集合U中 以后每一步从一个顶点在U中 而另一个顶点不在U中的各条边中选择权值最小的边 u v 把它的顶点加入到集合U中 如此继续下去 直到网络中的所有顶点都加入到生成树顶点集合U中为止 用普里姆算法构造最小生成树的过程 0 在Prim算法运算过程当中 需要知道哪些信息 1 V集合内各顶点距离U内权值最小的边的权值 2 V集合内各顶点距离U内哪个顶
9、点最近 权值最小 U 当前生成树顶点集合 V 不属于当前生成树的顶点集合 采用邻接矩阵来存储图 为了实现上述思想 必须定义2个辅助数组 lowcost 存放顶点集合V 生成树外 内的各顶点到顶点集合U 生成树顶点集合 内的权值最小的边的权值 nearvex 记录顶点集合V 生成树外 内的各顶点距离顶点集合U 生成树顶点集合 内哪个顶点最近 权值最小 从顶点0出发 2个辅助数组的初始状态为 lowcost nearvex V 5选边 0 5 因为在生成树顶点集合内最初只有一个顶点0 因此在nearvex数组中 只有表示顶点0的数组元素nearvex 0 1 其他都是0 表示集合外各顶点距离集合内
10、最近的顶点是0 数组lowcost表示生成树顶点集合 目前只有顶点0 顶点到生成树外各顶点的边的最小权值 初始值为邻接矩阵中顶点0所在的行 在prim算法里要重复做以下工作 简化 在lowcost 中选择nearvex i 1且lowcost i 最小的顶点i 用v标记它 将nearvex v 改为 1 表示它已经加入到生成树顶点的集合 修改lowcost 修改nearvex 在prim算法里要重复做以下工作 具体 在lowcost 中选择nearvex i 1且lowcost i 最小的顶点i 用v标记它 则选中的权值最小的边为 nearvex v v 相应的权值为lowcost v 如第一
11、次选中的v 5 则边 0 5 是选中的权值最小的边 相应的权值为lowcost 5 10 将nearvex v 改为 1 表示它已经加入到生成树顶点的集合 将边 nearvex v v lowcost v 输出来 修改lowcost 注意 原来顶点v不属于生成树顶点集合 现在v加入进来了 则顶点集合V 生成树外 内的各顶点到顶点集合U 生成树顶点集合 内的权值最小的边的权值lowcost i min lowcost i Edge v i 即用V集合内各顶点i到加入集合U的新顶点v的距离 Edge v i 与原来它们到集合U中顶点的最短距离 lowcost i 做比较 取距离近的 作为这些集合外
12、顶点到生成树顶点集合内顶点的最短距离 修改nearvex 如果顶点集合V内顶点i到顶点v的距离比原来它到顶点集合U中顶点的最短距离还要近 则修改nearvex i nearvex i v 表示生成树外顶点i到生成树内顶点v当前距离最近 lowcost nearvex V 4 选边 5 4 lowcost nearvex V 3 选边 4 3 lowcost nearvex V 2 选边 3 2 lowcost nearvex V 1 选边 2 1 lowcost nearvex V 6 选边 1 6 lowcost nearvex lowcost nearvex V 5 选边 0 5 0 de
13、fineMAX100000 defineMAX VER NUM10 顶点个数最大值intEdge MAX VER NUM MAX VER NUM 邻接矩阵intvernum 顶点个数 假设邻接矩阵和顶点个数已经读进来了voidPrim int lowcost newint vernum int nearvex newint vernum for inti 0 i verNum i lowcost i Edge 0 i nearvex i 0 nearvex 0 1 for i 1 i verNum i intmin MAX intv 0 for intj 0 j vernum j if nea
14、rvex j 1 endif endfor endprim 1 2 3 4 算法分析 上述算法的初始化时间是O 1 k循环中有两个循环语句 其时间大致为 令O 1 为某一正常数C 展开上述求和公式可知其数量级仍是n的平方 所以 整个算法的时间复杂性是O n2 Prim算法的优化 lowcost数组和nearvex数组是不是可以合二为一 见ZOJ1586的解题报告 MST例子 ZOJ1203ZOJ1406解题报告 ZOJ1586 问题 对于一个给定的无向连通图 它的MST是唯一的吗 答案 MST权值总和是唯一的 但有可能可以选择不同的边 POJ1679TheUniqueMST第2届校内赛 ProblemA AnotherMST
