-最小生成树VIP专享VIP免费

最小生成树陈旭龙•对于一张图进行深度优先搜索或者广度优先搜索，可生成一棵搜索树。搜索的出发点不同，生成树的形态亦不同。•在一张带权的无向连通图中，各边权和为最小的一棵生成树即为最小生成树。应用举例•已知某乡管辖的村庄都是有路可通的，且相邻村庄间公路的长度已知。现在要沿公路架设电线，使各村之间都通电话，问应该怎样架线才能使所用的电线最少。最小生成树的计算策略•计算最小生成树采用的是贪心策略，即必须保证每次添加的边同时满足下述两个条件：•（1）不能形成回路；•（2）在保证条件1的前提下添加权尽可能小的边，这样的边称之为安全边。Kruskal算法•初始时，森林是由单个节点组成的n棵树。然后反复找出森林中连接任意两棵树的所有边中具有最下权值的边（u,v），将其作为安全边，把它添加到正在生长的森林中，直至产生最小生成树为止。12345678Kruskal算法思路•设节点数n，边数为m；所有边按照权值递增的顺序排列成边集e，其中第i条边为（e[i].x,e[i].y），该边的权为e[i].c；并查集为f，其中f[i]为节点i所在并查集的代表节点，即子树根。主算法如下：procedurekruskal{qsort(1,n);//按照边权值递增的顺序排序边集efori:=1tondof[i]:=i;//并查集，初始化每棵树fori:=1tomdounion(e[i].x,e[i].y,e[i].c)}procedureunion(i,j,c:longint);varx,y:longint;{x:=getfather(i);y:=getfather(j);ifx<>ythen{inc(ans,s);f[y]:=x;}}functiongetfather(i:longint):longint;{ifi<>f[i]thenf[i]:=getfather(f[i]);exit(f[i]);}Kruskal算法总运行时间为O（ElnE），算法效率取决于边数E，适用于稀疏图。kruskal•P1442繁忙的都市•P1352Kerry的电缆网络•P1470口袋的天空•P1374新年趣事之游戏•Poj2421•Poj1861•Poj3522•poj1679Prim算法•Prim算法执行过程中，集合A中的边总是只形成单棵树。初始时，A为空。接下来每次添加到A的边都是使树的边尽可能小的边，这个过程一直进行到不存在连接生成树的边为止。Prim算法思路•设r为出发节点，w[i,j]为边(i,j)的权。若图中不存在边(i,j)，则w[i,j]=∞。ans为最小树的和，d[i]为生成树外节点i与生成树相连的最短边长，即d[i]=min{w[i,j]}(i不属于最小生成树t，j属于最小生成树t)，简称节点i的距离值。•在算法执行过程中，所有不在树中的节点按照d值递增的顺序组成一个优先队列；f[u]为树中u节点的父母。ProcedureMST_Prim;{foreachv∈G(v)do{d[v]:=∞;f[u]:=nil};d[r]:=0;Q:=G(v);whileQ<>∮do{在队列Q中取出一个d值最小的节点u；ifu<>rthenans:=ans+w[u,f[u]];foreachv∈adj[u]doif(v∈Q)and(w[u,v]