最小生成树

Q：什么是广度优先搜索

A：一个连通图的生成树含有图中全部的顶点，并且只含尽可能少的边。若砍去它的一条边，则会使生成树变成非连通图。若给它增加一条边，则会形成图中的一条回路。

对于一个带权连通无向图 G=(V, E) ，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树），称为G的最小生成树。

通过定义不难看出，最小生成树具有以下性质：

1）最小生成树不是唯一的，即最小生成树的树形不唯一，所有生成树中可能有多个最小生成树。当图 G 中的各边权值互不相等时，G 的最小生成树是唯一的。 若无向连通图 G 的边数比顶点数少1，即 G 本身是一棵树时，则 G 的最小生成树就是它本身。

2）最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。

3）最小生成树的边数为顶点数减1。

构造最小生成树 有多种算法，但大多数算法都利用了最小生成树的下列性质：假设  G=(V,E) 是一个带权连通无向图，U 是顶点集 V 的一个非空子集。若 (u，v) 是一条具有最小权值的边，其中  u∈U,v∈V−U , 则必存在一棵包含边 (u，v) 的最小生成树。

下面介绍一个通用的最小生成树算法：

GENERIC_MST(G){
  T=NULL;
  while T 未形成一棵生成树;
  do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
    T=T ∪ (u, v);
}

通用算法每次加入一条边以逐渐形成一棵生成树，下面介绍两种实现上述通用算法的途径。

Prim算法实现最小生成树

Q：如何通过Prim算法构建最小生成树

A：初始时从图中任取一顶点加入树 T，此时树中只含有一个顶点。之后选择一个与当前 T 中顶点集合距离最近的顶点，并将该顶点和相应的边加入 T。每次操作后 T 中的顶点数和边数都增 1。以此类推，直至图中所有的顶点都并入 T，得到的 T 就是最小生成树。此时 T 中必然有 n-1条边。

通俗来讲，Prim算法构建最小生成树流程如下：

1） 从某顶点 u0 出发，选择与它关联的具有最小权值的边 (u0, v)，将其顶点 v 加入到生成树的顶点集合 U 中。

2） 每一步从一个顶点在 U 中，而另一个顶点不在 U 中的各条边中选择权值最小的边 (u, v),把它的顶点 v 加入到 U 中。

3）直到所有顶点都加入到生成树顶点集合 U 中为止。

Prim算法的简单实现如下：

void Prim(G,T)
{
  t=NULL;    //初始化空树 
  U={w};    //添加任一结点 w
  while((V-U)!=NULL)  //若树中不含全部结点
  {
  设（u，v）是使 u∈U与v∈（V-U），且权值最小的边；
  T=T∪{{u，v}} //边归入树 
  U=U∪{v}；  //顶点归入树 
  } 
}

Prim 算法的时间复杂度为 O(n^2),不依赖于|E|，因此它适用于求解边稠密的图的最小生成树。

kruskal算法实现最小生成树

与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Q：如何通过kruskal算法构建最小生成树

A：初始时为只有 n 个顶点而无边的非连通图 T=V，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入 T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 T 中所有顶点都在一个连通分量上。

通俗来讲，kruskal算法构建最小生成树流程如下：

1）设连通网络 N = { V, E }，构造一个只有 n 个顶点，没有边的非连通图 T = { V, Ø }, 每个顶点自成一个连通分量。

2） 在 E 中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入 T 中；否则舍去，重新选择。

3）重复下去，直到所有顶点在同一连通分量上为止。

kruskal算法的简单实现如下：：

void Kruskal(V,T)
{
  T=V;    //初始化树T，仅含顶点
  numS=n    //连通分量数
  while(numS>1){  //若连通分量数大于 1 
  从 E 中取出权值最小的边（v,u）; 
  T=T ∪{{v,u}}; //将此边加入生成树中 
  numS--;   //连通分量减 1 
  } 
}

kruskal 算法的时间复杂度为 O(ElogE) ，因此它适用于求解边稀疏而顶点多的图的最小生成树。