图算法之最小生成树(Kruskal)

原 作者 张根 | 发表于 | 分类于 2014级

所谓最小生成树是指：给定一个无向图G={V,E}，用集合{u,v}∈E表示从u到v的边，w(u,v)表示从u到v的权值，若{u,v}集合中所有元素权值之和最小且没有构成回路，则称集合{u,v}为该图的最小生成树。举个例子，如下图所示的连通图中，其中的一个最小生成树为边：（A，C）、（A，D）、（D，B）、（D，F）、（B，E）、（E、G）组成的树。

QQ截图20160126210813

最小生成树在现实生活中的应用也很广泛，比如现在要对ABCDEFG这几个小区进行网络布线，给出了上图的村庄分布，求成本最小的方案。这里就可以用生成树来达到布线总距离最短，达到节约成本的目的。

Kruskal算法是图中计算最小生成树的算法之一。该算法由Joseph Kruskal在1956年发表。

Kruskal算法的核心思想是：

(1)、新建图G，图G中只有原图的顶点但是没有原图中的边。

(2)、按照权值由小到大对原图的边进行排序。

(3)、将原图中排序完的边进行由小到大选取边，如果该边加入后没有构成回路则选取，反之不选取。

(4)、重复步骤(3)直到所有的顶点都位于同一个连通分量中。

在实际的执行过程中判断有没有回路可以看两个顶点是否在同一个集合内，在同一集合内则表明构成了回路否则没有构成回路。还是以上图为例，Kruskal算法的执行过程如下：

  1. 、对权值数组进行排序得到(A，C)、(B，D)、(D，F)、(E，G)、(A，D)、(B，E)、(C，F)、(A，B)、(D，G)、(F，G)
  2. 、（目前已加入生成树的集合为空集）按顺序选取(A，C)发现A和C没有在已生成的某个集合内，所以可以选取，并且生成了已加入生成树集合{AC}。
  3. 、（目前已加入生成树的集合为{AC}）再选取(B，D)发现B和D没有在同一个集合，所以可以选取，并且生成了集合{BD}。
  4. 、（目前已加入生成树的集合为{AC}、{BD}）再选取(D、F)发现D和F没有在同一集合，所以可以选取，并生成集合{DF}，因为与{BD}共有一个D，所以将{DF}与{BD}合并为{BDF}（此处原因可由图出发思考）。
  5. 、（目前已加入生成树的集合为{AC}、{BDF}）再选取(E、G)发现E和G没有在同一集合中，所以可以选取，并且生成集合{EG}。
  6. 、（目前已加入生成树的集合为{AC}、{BDF}）再选取(A，D)发现A和D也没有在同一个集合，所以可选，并且生成集合{AD}，同理，合并为{ABDF}，又合并为{ABCDF}
  7. 、（目前已加入生成树的集合为{ABCDF}、{EG}）再选取(B，E)发现B和E没有在同一个集合内，所以选取，并生成集合{BE}，合并后为{ABCDEFG}。

因为已经将所有的顶点都加入到同一个连通分量（同一集合）中，所以选取结束，最终结果是(A，C)、(B，D)、(D，F)、(E，G)、(A，D)、(B，E)，发现与之前的A，C）、（A，D）、（D，B）、（D，F）、（B，E）、（E、G）结果不一样，是不是计算错误呢？不是的，之前那个路径和为17，现在也是17，这就说明一个图的最小生成树可能存在多个。

代码：

//Kruskal算法,采用集合的形式描述,先将连通图所有的边存储进数组vex形如:起点,终点,权值
//按权值对vex数组进行升序排序,从中依次选取,如果起点和终点没有在同一个已加入生成树的集合内则将此边加入集合
//如果在同一集合则舍弃,直到选取顶点个数-1条边为止.
intKruskal(Graph *g,intstart,MiniSpanTreemini_span_tree[])
{
　　intcost=0,len=-1,i,j=0,m,n;
　　intparent[MAXSIZE];
　　EdgeNode *pTemp;
　　MiniSpanTreevex[MAXSIZE];
 
　　//将边以起点,终点,权值的形式整合进vex数组
　　for(i=0;i<g->len;++i){
　　　　pTemp=g->v[i].pHead.pNext;
　　　　while(pTemp){
　　　　　　if(pTemp->pos>i){
　　　　　　　　++len;
　　　　　　　　vex[len].start=i;
　　　　　　　　vex[len].end=pTemp->pos;
　　　　　　　　vex[len].weight=pTemp->weight;
　　　　　　}
　　　　　　pTemp=pTemp->pNext;
　　　　}
　　　}
　　//排序
　　sort(vex,0,len);
 
　　//对parent数组进行初始化
　　//该数组将下标当作起点,内容当作终点,构成一个小的路径数组
　　//初始化为-1是为了防止与下标0起冲突
　　for(i=0;i<=len;++i){
　　　　parent[i]=-1;
　　}
　　//循环的结束条件是要么将数组中的内容全部扫描一遍
　　//要么生成树的顶点-1条边全部已经筛选出来
　　for(i=0;i<=len&&j!=g->len-1;++i){
　　　　//检查是否在同一集合可以将起点和终点分别当成两个起点
　　　　//从两个点出发,直到在parent数组中无路可走(终点)时
　　　　//若两个终点相同则表明在同一集合,反之则不在同一集合
　　　　//因为可以将两个起点构成的路径看作两个线(线性结构,没有分叉),如果末端相交则一定相交,末端不相交则不会相交
　　　　n=FindRow(parent,vex[i].start);
　　　　m=FindRow(parent,vex[i].end);
　　　　if(m!=n){
　　　　　　parent[n]=m;
　　　　　　mini_span_tree[j]=vex[i];
　　　　　　cost+=vex[i].weight;
　　　　　　++j;
　　　　}
　　　}
 
　　returncost;
}
 
//以front为起点寻找连线结点的尾部结点下标
intFindRow(intparent[],intfront)
{
　　while(parent[front]>=0){
　　　　front=parent[front];
　　}
 
　　returnfront;
}