04-最小生成树问题

1、最小生成树 对于一张图进行深度优先搜索或者广度优先搜索，可生成 一棵搜索树。搜索的出发点不同，生成树的形态亦不同。 在一张带权的无向连通图中，各边权和为最小的一棵生成 树即为最小生成树。 应用举例 已知某乡管辖的村庄都是有路可通的，且相邻村庄间公路 的长度已知。现在要沿公路架设电线，使各村之间都通电 话，问应该怎样架线才能使所用的电线最少。 最小生成树的计算策略 计算最小生成树采用的是贪心策略，即必须保证每次添加 的边同时满足下述两个条件： （1）不能形成回路； （2）在保证条件1的前提下添加权尽可能小的边，这样的 边称之为安全边。 Kruskal算法 初始时，森林是由单个节点组成的n棵树。然

2、后反复找出 森林中连接任意两棵树的所有边中具有最下权值的边（u,v ），将其作为安全边，把它添加到正在生长的森林中，直 至产生最小生成树为止。 123 456 78 Kruskal算法思路 设节点数n，边数为m；所有边按照权值递增的顺序排列成边集e，其中 第i条边为（ei.x,ei.y），该边的权为ei.c；并查集为f，其中fi为节点 i所在并查集的代表节点，即子树根。主算法如下： procedure kruskal qsort(1,n);/按照边权值递增的顺序排序边集e for i:=1 to n do fi:=i;/并查集，初始化每棵树 for i:=1 to m do union(ei.

3、x,ei.y,ei.c) procedure union(i,j,c:longint); var x,y:longint; x:=getfather(i);y:=getfather(j); if xy then inc(ans,s);fy:=x; function getfather(i:longint):longint; if ifi then fi:=getfather(fi); exit(fi); Kruskal算法总 运行时间为O （ElnE），算 法效率取决于 边数E，适用 于稀疏图。 kruskal P1442 繁忙的都市 P1352 Kerry 的电缆网络 P1470 口袋的天空

4、 P1374 新年趣事之游戏 POJ 2421 Constructing Roads POJ 1861 Network POJ 3522 Slim Span POJ 1679 The Unique MST Prim算法 Prim算法执行过程中，集合A中的边总是只形成单棵树。 初始时，A为空。接下来每次添加到A的边都是使树的边尽 可能小的边，这个过程一直进行到不存在连接生成树的边 为止。 Prim算法思路 设r为出发节点，wi,j为边(i,j)的权。若图中不存在边(i,j)，则wi,j=。 ans为最小树的和，di为生成树外节点i与生成树相连的最短边长，即 di=minwi,j(i不属于最小生成

5、树t，j属于最小生成树t)，简称节点i的 距离值。 在算法执行过程中，所有不在树中的节点按照d值递增的顺序组成一个 优先队列；fu为树中u节点的父母。 Procedure MST_Prim; for each vG(v) do dv:=;fu:=nil; dr:=0;Q:=G(v); while Q do 在队列Q中取出一个d值最小的节点u； if ur then ans:=ans+wu,fu; for each vadju do if (vQ) and (wu,vdv) then fv:=u;dv:=wu,v; 输出最小生成树的权和ans; Prim算法的整个运行时 间为O（VlnV+Eln

6、V）。 上限为O（VlnV+V2lnV）。 Prim算法的效率取决于 节点数V，一般使用于稠 密图。 void Prim() int dMax,VexSetMax,v; int i,j,k,min; for(i=0;ig.n;i+) di=g.edgesvi; VexSeti=0; VexSetv=1; sum=0; for(i=0;ig.n;i+) min = INF; for(j=0;jg.n;j+) if(VexSetj=0 k=j; VexSetk=1; v=k; sum+=min for(j=0;jg.n;j+) if(VexSetj=0 Prim算法的堆优化 prim POJ 12

7、58 Agri-Net POJ 1789 Truck History POJ 2485 Highways Kruskal算法每次在森林中的两棵树之间添加安全边，其算 法效率取决于边数，因此适用于稀疏图。 Prim算法每次在单棵树上添安全边，其算法效率取决于节 点数，因此适用于稠密图。 生成树相关问题 两个性质 （1）切割性质：假定所有边权均不相同。设S为既非空集 也非全集的V的子集，边e是满足一个端点在s内，另一个 端点不在s内的所有边中权值最小的一个，则图G的所有生 成树均包含e。 （2）回路性质：假定所有边权值均不相同。设C是图G中 的任意回路，边e是C上权值最大的边，则图G的所有生成 树

8、均不含e。 增量最小生成树 从包含n个点的空图开始，依次加入m条带权边。每加入一 条边，输出当前图中的最小生成树权值（如果当前图不连 通，输出无解） 如果每次重新求解完整的最小生成树，总时间复杂度高达O （m2*logn）。 算法：求出最小生成树后，将其它边删除。之后每次加入一条边e=（u， v），则图中恰好包含一个环。根据回路性质，删除该回路上权值最大 的边即可，因此只需在加边之前的MST上找到u到v的唯一路径上权值最 大的边，再和e比较，删除权值较大的一条。由于路径唯一，可以用DFS 或者BFS找到这条u到v的路径，总时间复杂度为O(nm)。 最小瓶颈树 给出加权无向图，求一棵生成树，使得

9、最大边权值尽量小 由于只关心最大边权值，可以从一个空图开始，按照权值从小到大的 顺序依次加入各条边，则图第一次连通时，该图的最小生成树就是原 图的最小瓶颈生成树。 这就是Kruskal算法 最小瓶颈路 给定加权无向图的两个结点u和v，求出从u到v的一条路径 ，使得路径上的最长边尽量短 用DFS枚举u到v的每一条路径？ 先求出该图的最小生成树，则起点和终点在树上的唯一路径就是所要找的 路径，这条路径上的最长边就是最小瓶颈路。 每对结点间的最小瓶颈路 给出加权无向图，求每两个结点u和v之间的最小瓶颈路的 最大边长f（u,v） 1、先求出最小生成树 2、用DFS把最小生成树变成有根树，同时计算f(u

10、,v)。 3、结合最近公共祖先tarjan算法，当访问结点u时，w是u的father，对于所 有已经访问过的结点v，存在f(u,v)=max(f(w,v),e(u,w)。 时间复杂度O(n2) 次小生成树 把所有生成树按照权值之和从大到小的顺序排列，求排在 第二位的生成树。如果最小生成树不唯一，次小生成树的 权值和最小生成树相同 次小生成树不会和最小生成树完全相同，因此可以枚举最小生成树中不在 次小生成树中出现的边。时间复杂度为O(nm(n,m)。 方法2：枚举要加入哪条新边。在最小生成树上加一条边u-v后，图上会出 现一条回路，因此删除的边必须在最小生成树上u到v的路径上，而且是这 条路径上的最