生成树的概念：

在一个无向图中，设顶点数为\(n\)，取其中\(n-1\)条边并使所有点相连，所得到的一棵树即为生成树。

最小生成树：

如果还没有接触过生成树的同学，欢迎戳->最小生成树详解

次小生成树：

次小生成树顾名思义，就是边权之和次小的一棵生成树。有严格次小生成树与非严格次小生成树之分。

尽管这个算法的名字叫做次小生成树，不过其实可以理解成一道数据结构

次小生成树可以和次短路径一起理解，有兴趣的同学可以做做模板题

非严格次小生成树的边权之和不一定要比最小生成树的小，即\(Σw\)次≥\(Σw\)最

严格次小生成树的边权之和一定要比最小生成树的小，即\(Σw\)次>\(Σw\)最

想要求出次小生成树？

显然我们可以dfs求出所有的生成树，在排序选出严格次小的就可以了。

但是上述方法显然不能快速求出次小生成树

为了快速的求出来次小生成树，我们需要知道一个结论：次小生成树和最小生成树之间只有一条边的差异。

这一条结论为什么是正确的呢？

我们先来看看\(Kruskal\)是怎么求最小生成树的

\(Kruskal\)是按照边权排序，按照贪心的思路一条一条的加进树边，所以如果要求出次小生成树，那么我们可以放弃一条小的边不选，加入另一条边使图联通。

如果我们"放弃"了两条边，那么只"放弃"一条边的生成树的边权和显然小于"放弃"两条边的生成树的边权和。

所以求出(非)严格次小生成树的朴素算法为：先建立一棵最小生成树。再枚举删去最小生成树上的每一条路径，再在新构成的生成树中选出一棵边权之和最小生成树的即可。

时间复杂度为\(O(nmlogm)\)。当然这种算法还不够优秀，我们可以继续优化

非严格次小生成树我们可以这样优化：

枚举边的时候，枚举没有被并入到最小生成树的边(我们将把这条边加入到生成树中，显然现在的图形不再是一棵树，所以我们要原图中删去一条最大边，使新图仍然联通)

加入边权值为\(W1\)。查询树上每一条的路径，在路径选取一个边权最大值\(W2\)。则当前枚举的答案为\(W−W2+W1\)(W为最小生成树的边权之和)

枚举所有的边之后，取最小值即可。

我们可以用倍增/树剖/LCT来实现查询树上最大值的操作，故复杂度为：\(O(mlogn)\)

再来看看严格次小生成树

不难发现：求非严格最小生成树时，枚举一条边\(W1\)，之后再寻找一条生成树上的最大边\(W2\)

显然\(W1≥W2\)，因此可能由此得到的次小生成树并非严格。所以我们可以在每次查询时，需要找到严格次小的\(W1\)，即\(W1>W2\)，这样我们就可以得到严格次小生成树了。

维护仍可以用倍增或者树剖思想。

这里介绍树剖的思路：

先用线段树维护区间最小值与严格次小值，如果是叶子节点最大值就设为他本身，次大值设为0

合并的时候把两个区间的这四个值(两个最大值与两个次大值)排序，再寻找最大值与严格次小值即可。

代码如下：

#include

using namespace std;

#define re register

#define il inline

#define int long long //把所有int转成longlong

#define debug printf("Now is line %d\n",__LINE__);

il int read()

{

re int x=0,f=1;char c=getchar();

while(c'9'){if(c=='-') f=-1;c=getchar();}

while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();

return x*f;

}//快读

#define maxm 300005

#define inf 12345678900000000

#define maxn 100005

struct Edge{int u,v,w,next;}e[maxm<<1];

struct qj{int ma,ma2;}q[maxn<<2];

struct Edge1

{

int u,v,w;

bool operator

}edge[maxm];

int n,m,vis[maxm],ans=inf,head[maxn],cnt,fa[maxn],mtree;

il void add(int u,int v,int w)

{

e[++cnt].v=v;

e[cnt].w=w;

e[cnt].next=head[u];

head[u]=cnt;

}//前向星加边

namespace smallesttree

{

il int find(int x)

{

while(x!=fa[x]) x=fa[x]=fa[fa[x]];

return x;

}//并查集找祖先

il void init()

{

for(re int i=1;i<=n;i++) fa[i]=i; //预处理并查集

for(re int i=0;i

}

il void kruskal()

{

init();

sort(edge,edge+m);

re int T=0;

for(re int i=0;i

{

re int eu=find(edge[i].u),ev=find(edge[i].v);//寻找祖先

if(eu!=ev)

{

add(edge[i].u,edge[i].v,edge[i].w),add(edge[i].v,edge[i].u,edge[i].w);

mtree+=edge[i].w;//记录子树大小

fa[ev]=eu;//合并

vis[i]=1;//标记该边为树边

if(++T==n-1) break;//边数等于节点数+1即为一颗树

}

}

}

}

//求出最小生成树

namespace treecut

{

int dep[maxn],father[maxn],top[maxn],W[maxn],a[maxn],size[maxn],son[maxn],seg[maxn],col;

//dep:深度 father:父亲节点 top:重链的顶端 W:到根节点的距离 a:点的权值 size:子树大小 son:重儿子 seg:在线段树中的序号(dfs序)

il void dfs1(int u,int fr)

{

dep[u]=dep[fr]+1;

size[u]=1;

father[u]=fr;

for(re int i=head[u];i;i=e[i].next)

{

re int v=e[i].v;

if(v!=fr)

{

W[v]=W[u]+e[i].w;//W为每一个点到根节点的距离

dfs1(v,u);

size[u]+=size[v];

if(size[v]>size[son[u]]) son[u]=v;

}

}

}//预处理出dep、size、father以及son

il void dfs2(int now,int fi)

{

top[now]=fi;

seg[now]=++col;

a[col]=W[now]-W[father[now]];//a为点的权值(它与之父亲节点边的权值)(相当于前缀和)

if(!son[now]) return;

dfs2(son[now],fi);

for(re int i=head[now];i;i=e[i].next)

{

re int v=e[i].v;

if(v!=son[now]&&v!=father[now]) dfs2(v,v);

}

}//预处理出每个节点的top、seg以及权值

//树剖模板就不解释了

#define ls k<<1

#define rs k<<1|1

il bool CMP(int a,int b){return a>b;}

il int getse(int x,int g,int z,int c)

{

re int a[5]={x,g,z,c};

sort(a,a+4,CMP);

for(re int i=1;i<3;++i)

{

if(a[i]!=a[0]) return a[i];

}

}//找到两个区间的最大值和严格次大值(四个数)的最大值与严格次大值

// 就是合并两个区间的最大值和严格次大值

il void build(int k,int l,int r)

{

if(l==r)

{

q[k].ma=a[l];

return;

}

re int mid=(l+r)>>1;

build(ls,l,mid),build(rs,mid+1,r);

q[k].ma=max(q[ls].ma,q[rs].ma);

q[k].ma2=getse(q[ls].ma,q[rs].ma,q[ls].ma2,q[rs].ma2);

}//预处理出区间最大值与次大值

il qj query(int k,int l,int r,int ll,int rr)

{

if(ll>r||rr

if(ll<=l&&rr>=r) return (qj){q[k].ma,q[k].ma2};

re int mid=(l+r)>>1;

re qj t1=query(ls,l,mid,ll,rr),t2=query(rs,mid+1,r,ll,rr);

return (qj){max(t1.ma,t2.ma),getse(t1.ma,t2.ma,t1.ma2,t2.ma2)};

}//查询区间的区间的最大值与次小值

il int LCA(int u,int v,int d)

{

re int need=-inf;

while(top[u]!=top[v])

{

if(dep[top[u]]

qj temp=query(1,1,n,seg[top[u]],seg[u]);

u=father[top[u]];

need=max(need,(temp.ma==d)?temp.ma2:temp.ma);//严格次小边(如果temp.ma==k就是非严格次小)

}

if(dep[u]

qj temp=query(1,1,n,seg[v]+1,seg[u]);

return max(need,(temp.ma==d)?temp.ma2:temp.ma);//同上

}

il void init()

{

dfs1(1,0),dfs2(1,1),build(1,1,n);

}

}

//树链剖分

signed main()

{

n=read(),m=read();

smallesttree::kruskal();//求出最小生成树

treecut::init();//预处理

for(re int i=0;i

{

if(vis[i]) continue;//枚举所有非树边(没有在最小生成树的边)

re int temp=mtree/*最小生成树边权和*/+edge[i].w/*本来的树边的边权*/-treecut::LCA(edge[i].u,edge[i].v,edge[i].w)/*找到严格次小边的边权*/;

if(ans>temp&&temp!=mtree+e[i].w/*其实就是严格此小边不为0(没有找到严格次小边)*/&&temp>mtree) ans=temp;

}

printf("%lld",ans);

return 0;

}

定义1   对于无向图G和一棵树T来说，如果T是G的子图，则称T为G的树，如果T是G的生成子图，则称T是G的生成树。

定义2   对于一个边上具有权值的图来说，其边权值和最小的生成树称做图G的最小生成树。

定理1    对于一个图G，如果图中的边权值都不相同，则图的最小生成树唯一。

最小生成树

求无向图的最小生成树主要有Prim算法和Kruskal算法。

1.Prim算法

(1)基本算法

将图G中的所有点V分成两个顶点集合Va和Vb。在计算过程中Va中的点为已经选好连接入生成树的点，否则属于Vb。最开始的时候Va包含任意选取的图G中的一个点u，其余的点属于Vb，算法结束时所有与u连通的点属于Va，其余的点仍留在Vb中。如果算法结束时Vb不为空，说明图G的生成树不存在，只存在生成森林。

代码如下：

1 //直接实现，邻接矩阵存储图

2 const int maxn=101;3 void Prim(int n,int dist[maxn],int map[maxn][maxn],intpre[maxn])4 //n个点，dist[i]表示向外延伸的最短边长，map记录图信息，pre[]记录连接信息，5 //dist之和最最小权值

6 {7 inti,j,k;8 intmin;9 bool p[maxn];//记录该点是否属于Va

10 for(i=2;i<=n;i++)11 {12 p[i]=false;13 dist[i]=map[1][i];14 pre[i]=1;15 }16 dist[1]=0;17 p[1]=true;18 for(i=1;i<=n-1;i++)//循环n-1次，每次加入一个点

19 {20 min=INT_MAX;21 k=0;22 for(j=1;j<=n;j++)23 {24 if(!p[j]&&dist[j]

31 p[k]=true;32 for(j=1;j<=n;j++)33 {34 if(!p[j]&&map[k][j]!=INT_MAX&&dist[j]>map[k][j])35 {36 dist[j]=map[k][j];37 pre[j]=k;38 }39 }40 }41 }42 //时间复杂度O(n^2);43

44 //堆实现

45 /*使用堆来保存Vb中每一点到Va中所有点的最短边长并维护其最小值，46 并在访问每条边的时候更新。先将所有的点插入堆，并将值赋为inf，47 将根赋值为0，通过松弛技术进行更新。*/

48 //堆

49 structHeapElement50 {51 intkey,value;52 };53 structMinHeap54 {55 HeapElement H[maxn];56 intsize;57 intposition[maxn];58 void init(){H[size=0].value=-INF;}59 void ins(int key,intvalue)60 void decrease(int key,intvalue)61 voiddelmin()62 }H;63 //边

64 structedge65 {66 intto,w,next;67 }edge[maxm];68 intN,M;69 long longdist[maxn];70 inthead[maxn];71 voidPrim()72 {73 inti,j,k;74 bool p[maxn]={0};75 H.init(true);76 for(i=1;i<=N;i++)77 {78 H.ins(i,INF);79 dist[i]=INF;80 }81 dist[1]=0;82 H.decrease(1,0);83 for(i=1;;)84 {85 p[i]=true;86 H.delmin();//删除堆顶元素

87 for(k=head[i];k!=-1;k=edge[k].next)88 {89 if(!p[j]&&edge[k].w

97 else break;98 }99 }100

101 /*用堆优化的Prim算法主要用于加速变较少的图的最小生成树的计算，特别是稀疏图。102 总的时间复杂度是O((n+m)log n).当边较少时，这种算法相对直接实现的Prim算法来说103 有很好的效果。*/

View Code

2.Kruskal算法

Kruskal算法基于贪心的思想，对于图G={V,E}，先构造G‘={V，Ø},然后依次向G’中添加E中未添加过的权值最小的边，如果这条边加入G‘中存在环，则去掉这条边，直到G’成为一棵树。

具体步骤：

①首先初始化，生成图G‘，并将E中的边按权值排序。

②从最小的边开始尝试加入到图G’中，如果当前便加入后存在环，则弃掉当前边，否则标记当前边并计数。

③遍历所有边后，如果选择的边数等于n-1，则生成最小生成树，计算步骤②所选择的边的权值之和，否则最小生成树不存在，只存在最小生成森林，但是Kruskal算法不需要反复运行，当前结果就是图G的最小生成森林。

算法的关键在于如何判断新加入的边会使图G‘产生环，这里使用并查集，并查集中的一个等价类代表图G’中的一个连通分量，也就是一棵树，如果新加入边的两端在并查集的一个等价类中，说明存在环，需要舍掉这条边；否则保留当前边，并合并涉及的两个等价类。

代码如下：

1 //并查集

2 const in maxn=1010;3 intUFSTree[maxn];4 int find(intx);5 void merge(int x,inty)6 //Kruskal

7 const int maxm=100010;8 structnode9 {10 int a,b;//边的起点和终点

11 intw;12 bool select;13 }edge[maxm];14 boolcmp(node a,node b)15 {16 if(a.w!=b.w)return a.w

28 x=find(edge[i].a);29 y=find(edge[i].b);30 if(x!=y)31 {32 merge(x,y);33 k++;34 edge[i].select=true;35 }36 }37 }

View Code

时间复杂度为O(mlog m + m),即主要的时间都花在边的排序上了。个人觉得该算法好理解、好操作。

次小生成树

次小生成树的边的权值和可能等于最小生成树的权值和，或者略大。

定义1    设G={V,E}是连通的无向图，T是图G的一棵最小生成树。如果有另一棵树T1，T1≠T，满足不存在T‘，T’≠T，w(T')

定理1     存在边(u,v) ∈T和(x,y)不属于T满足T\(u,v)U(x,y)是图的一棵次小生成树。

基于定理1，那么所有的T\(u,v)U(x,y)刚好构成了T的邻集，则T的邻集中权值最小的就是次小生成树了。(定义由最小生成树T进行一次可行交换得到的新的生成树所组成的集合，称为树T的邻集，记为N(T)。所谓的可行交换即去掉T中的一条边，再新加入图G中的一条边，使得新生成的图仍为树。)

效率较高的做法是先加入(x,y)，对于一棵树，加入(x,y)后一定成为环，如果删去环上除(x,y)以外的最大的一条边，会得到加入(x,y)时权值最小的一棵树。如果能够快速计算最小生成树中点x到y之间路径中最长边的长度，这个问题就能很好地解决。最小生成树中x到y的最长边可以使用树形动态规划或者LCA等方法在O(n^2)的时间复杂度内算出。如果使用Kruskal算法求最小生成树，可以在算法的运行过程中求出x到y路径上的最长边，因为每次合并两个等价类的时候，分别属于两个等价类的两个点间的最长边一定是当前加入的，按照这条性质记录的话就可以求出所有值了。为了便于合并时的修改，需要记录每个集合都有哪些点，可以写一个类似邻接表的数据结构，将以i为代表元的集合的所有点作为i的邻接点进行存储。

具体实现如下：

在Kruskal算法的基础上进行修改，加入对x,y两点在最小生成树上路径中最长边的计算，存入length[][]数组。使用链式前向星记录每个集合都有哪些点。为了合并方便，除了head[]记录每条邻接表的头结点位置外，end[]记录每条邻接表尾节点的位置便于两条邻接表合并。mst为最小生成树的大小，secmst为次小生成树的大小。

代码如下：

1 //并查集

2 const in maxn=1010;3 intUFSTree[maxn];4 int find(intx);5 void merge(int x,inty)6 //Kruskal

7 const int maxm=100010;8 structnode9 {10 int a,b;//边的起点和终点

11 intw;12 bool select;13 }edge[maxm];14 boolcmp(node a,node b)15 {16 if(a.w!=b.w)return a.w

21 structnode122 {23 intto,next;24 };25 node1 link[maxn];//边数组,注意这里是maxn，而不是maxm，是类似的链式前向星

26 int il;//边数组中数据的个数

27 int head[maxn];//邻接表的头结点位置

28 int end[maxn];//邻接表的尾节点位置

29 int length[maxn][maxn];//每两点在最小生成树上路径中最长边长

30

31 void Kruskal(node *edge,int n,intm)32 {33 int k=0;34 inti,x,y;35 //初始化邻接表，对于每个节点添加一条指向其自身的边，表示以i为代表元的集合只有i

36 for(il=0;il

47 if(edge[i].w<0)continue;48 x=find(edge[i].a);49 y=find(edge[i].b);50 if(x!=y)51 {52 //修改部分，遍历两个节点所在的集合

53 for(w=head[x];w!=-1;w=link[w].next)54 {55 for(v=head[y];v!=-1;v=link[v].next)56 {57 int pp=link[w].to,qq=link[v].to;58 length[pp][qq]=length[qq][pp]=edge[i].w;59 }60 }61 link[end[y]].next=head[x];62 end[y]=end[x];63 merge(x,y);64 k++;65 edge[i].select=true;66 }67 }68 }69

70 intmain()71 {72 //先初始化和建图，然后进行下面的操作

73 intmst,secmst;74 Kruskal(edge,n,m);75 mst=0;76 for(i=1;i<=m;i++)77 {78 if(edge[i].select)mst+=edge[i].w;79 }80 secmst=INF;81 for(i=1;i<=m;i++)82 {83 if(!edge[i].select)secmst=min(secmst,mst+

84 edge[i].w-length[edge[i].a][edge[i].b]);85 }86 }

View Code

整个算法运行了一次Kruskal算法，时间复杂度是O(mlogm),同时又对整个length[][]进行赋值，时间复杂度O(n^2),最终又进行了时间复杂度为O(m)的遍历，所以总的时间复杂度为O(mlogm+n^2)。

有向图的最小树形图

首先看一个例子，有一处水源给附近的菜地供水，在没有抽水机的情况下，水只能从高处流向低处，每修一条水渠都有一定的花费，问怎样修才能使花费最低。考虑到水的流向，要求生成的最小生成树必须以水源为根，而且需要能够由根到达所有的节点。这就是最小树形图问题。

定义1    最小树形图的定义：

设G=(V,E)是一个有向图，如果具有以下性质：

(1)G中不包含有向环；

(2)存在一个顶点Vi，他不是任何弧的终点，而V的其他顶点都恰好是唯一的一条弧的终点。则称G是以Vi为根的树形图。

基本算法:

最小树形图基于贪心的思想和缩点的思想。所谓缩点，就是将几个点看成一个点，所有连接到这几个点的边都视为连到收缩点，所以从这几个点连出的边都被视为从收缩点连出。

下面根节点取为V0.

(1)求最短弧集合E0

从所有以Vi(i!=0)为终点的弧中去一条最短的，若对于点Vi，没有入边，则不存在最小树形图，算法结束；如果能取，则得到由n个点和n-1条边组成的图G的一个子图G‘，该子图的权值一定是最小的，但是不一定是一棵树。

(2)检查E0

若E0没有有向环且不含收缩点，则计算结束，E0就是G的以V0为根的最小树形图。若E0没有有向环、但含收缩点，则转步骤(4)，若E0含有有向环，则转入步骤(3)。

(3)收缩G中的有向环

把G中的C收缩成点u，对于图G中两端都属于C的边被收缩掉了，其他弧扔保留，得到一个新的图G1，G1中以收缩点为终点的弧的长度要变化，变化的规律是：设点v在环C中，且环中指向v的边长为w，点v'不在环C中，则对于每条边与其对应，且权重为w()-w；对于图G中以环C为起点的边，在图G1中有边,权重为w()。在此步生成的图G1中可能存在重边。

对于图G和图G1：

①如果图G1中没有以V0为根的最小树形图，则图G也没有。

②如果图G1中有以V0为根的最小树形图，则可以按照步骤(4)的展开方法得到图G的最小树形图。

因此，此时需要将G1带入步骤(1)做为图G继续进行计算，反复计算直到图G1的最小树形图求出。

(4)展开收缩点

如果图G1的最小树形图T1已经求出，那么所有T1的弧都属于T。将图G1的一个收缩点u展开成环C，从C中去掉与T1中有相同终点的弧，其他弧都属于T。

在计算的过程中可以发现，图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和，在这种性质的影响下，如果不需要知道最终的T0中到底需要那几条边，只需要知道T0的权值时，可以不需要展开。

下面给出只是求权值的代码：

1 double zhuliu(int n,doublemap[maxn][maxn])2 {3 boolvis[maxn];4 bool flag[maxn];//缩点标记为true，则该点已经被收缩，否则仍然存在

5 intpre[maxn];6 double sum=0;7 inti,j,k;8 for(i=0;i

17 for(i=1;i

26 for(i=1;i

30 for(j=0;j

34 {35 vis[j]=true;36 j=pre[j];37 }while(!vis[j]);38 if(!j)continue;//没有找到环

39 i=j;40 //将整个环的权值保存，累计入原图的最小树形图

41 do

42 {43 sum+=map[pre[j]][j];44 j=pre[j];45 }while(j!=i);46 j=i;47 //对与环上的点有关的边，修改边权

48 do

49 {50 for(k=0;k

56 for(j=0;j

66 for(j=pre[i];j!=i;j=pre[j])flag[j]=true;67 //当前环缩点结束，形成新的图G‘，跳出继续求G’的最小树形图

68 break;69 }70 //如果所有的点都被检查，且没有环存在，71 //现在的最短弧集合E0就是最小树形图，累计入sum,算法结束

72 if(i==n)73 {74 for(i=1;i

View Code

时间复杂度为O(n^3)。

参考文献《图论及应用》哈尔滨工业大学出版社

特此申明：严禁转载

2014-02-19

在图论的数学领域中，如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

常用的生成树算法有DFS生成树、BFS生成树、PRIM 最小生成树和Kruskal最小生成树算法。

中文名

生成树算法

外文名

Spanning tree algorithm

归属学科

图论包    括

DFS、BFS、最小生成树

图的生成树

不惟一

应    用

自动控制

生成树算法自由树

编辑

语音

自由树就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根，则成为一棵通常的树)。从根开始，为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序，则它就成为一棵有序树。在图的应用中，我们常常需要求给定图的一个子图，使该子图是一棵树。

生成树算法生成树

编辑

语音

在图论中，如果连通图 的一个子图是一棵包含的所有顶点的树，则该子图称为G的生成树(SpanningTree)。

生成树是连通图的包含图中的所有顶点的极小连通子图。

图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

通用定义：

若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。

(1)若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。

(2)若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。

(3)若G是非连通的无向图，则要若干次从外部调用DFS(或BFS)算法，才能完成对G的遍历。每一次外部调用，只能访问到G的一个连通分量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。

(4)若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。

生成树算法分类

编辑

语音

1)生成树的求解方法

设图是一个具有n个顶点的连通图。则从G的任一顶点(源点)出发，作一次深度优先搜索(广度优先搜索)，搜索到的n个顶点和搜索过程中从一个已访问过的顶点搜索到一个未曾访问过的邻接点，所经过的边(共n-1条)组成的极小连通子图就是生成树。(源点是生成树的根)

通常，由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。

注意：

①图的广度优先生成树的树高不会超过该图其它生成树的高度

②图的生成树不惟一，从不同的顶点出发进行遍历，可以得到不同的生成树。

生成树算法最小生成树

编辑

语音

对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：

其中，TE表示T的边集，w(u，v)表示边(u，v)的权。权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。[1]

普里姆(PRIM)算法

算法简单描述

1)输入：一个加权连通图，其中顶点集合为V，边集合为E；

2)初始化：Vnew= {x}，其中x为集合V中的任一节点(起始点)，Enew= {}，为空；

3)重复下列操作，直到Vnew= V：

a. 在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V(如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一)；

b. 将v加入集合Vnew中，将边加入集合Enew中；

4)输出：使用集合Vnew和Enew来描述所得到的最小生成树。[2]

伪代码描述PrimMST(G，T，r)

{

//求图G的以r为根的MST，结果放在T=(U，TE)中

InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)

for(k=0；k

{

//求T的n-1条树边

(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；

T←T∪{(u，v)

}；

//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U

ModifyCandidateSet(…)；

//根据新红点v调整候选轻边集

}

}

用普里姆算法构造最小生成树的过程

克鲁斯卡尔(Kruskal) 算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。

算法流程：

输入：图G

输出：图G的最小生成树

具体流程：

1)将图G看做一个森林，每个顶点为一棵独立的树

2)将所有的边加入集合S，即一开始S=E

3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E'

4)重复(3)直到所有点属于同一棵树，边集E'就是一棵最小生成树

时间复杂度：

Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环|E|次，所以这一步的时间复杂度为O(|E|α(V))，其中α为Ackermann函数，其增长非常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。

Kruskal算法构造最小生成树的过程

生成树算法应用

编辑

语音

网络G表示n各城市之间的通信线路网线路(其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。参考资料

1.

Gower J C, Ross G J S. Minimum Spanning Trees and Single Linkage Cluster Analysis[J]. Journal of the Royal Statistical Society, 1969, 18(1):54-64.

2.

江波, 张黎, JIANGBo,等. 基于Prim算法的最小生成树优化研究[J]. 计算机工程与设计, 2009, 30(13):3244-3247.