【算法导论】第23章最小生成树

　　因为之前的一章写了贪心算法，最小生成树也是贪心算法的一个应用，这里就先总结一下第23章，本来上周末就能搞定的，不过呆在寝室就不想做，所以就拖到了现在，话说武汉的夏天太热了，，，

1、问题引入

　　设计电子线路时，常常要把多个元件的引脚连接到一起，使其电位相同，要使n个引脚互相连通，可以使用n-1条连接线，每条连接线需要一定长度，所以总想找出使用连接线长度最短的连接方式，可以把这一连接线问题模型化为一个无相连通图（v,e），v是引脚集合，e是每对引脚之间可能互联的集合，对于图中的每一条边（u，v）属于e，都有一个权值w（u，v）表示连接u和v的代价（连线的长度），我们希望找到一个无回路的子集t属于e，它连接了所有的顶点，且其权值之和最小。因为t无回路且连接了所有的顶点，所以它必然是一棵树，称为生成树，就把确定树t的问题称为最小生成树问题，

　　这里主要给出解决最小生成树问题的两种算法：kruskal算法和prim算法。

2.1 kruskal算法

　　kruskal算法找出森林中连接任意两棵树的所有边中，具有最小权值的边（u，v）作为安全边，并把它添加到正在生长的森林中，设c1，c2表示边（u，v）连接的两棵树，因为（u，v）必是连接c1和其他某棵树的一条轻边，（u，v）对c1来说是安全边，kruskal算法是一种贪心算法，在算法的每一步中，添加到森林中的边的权值都是尽可能小的。

　　kruskal算法的实现采用了一种不相交集合数据结构（并查集），以维护几个互不相交的元素集合，其算法主要思路是：首先根据顶点数目建立|v|棵树，每棵树包含图中的一个顶点；对图中的边按照非递减顺序进行拍u；然后检查每条边，其端点u和v是否属于同一棵树，如果是，就放弃该边，否则说明两个顶点分属于不同的树，则对两个顶点所在的树进行合并。

　　kruskal算法中用到了（一种不相交集合数据结构-并查集），对并查集的理解参见：（并查集--学习详解http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.html）

　　kruskal算法的具体实现如下：

　　要生成最小生成树的图如下所示：

　　具体代码：

#include<stdio.h>
#include<stdlib.h>
#define n 9//图中点的个数
#define max 100
struct edge{
    int u;//起点
    int v;//终点
    int value;//边的权值
}e[max];
int p[max];//用于记录最小生成树的边
int father[n];//father[x]表示x的父节点；
int rank[n];//rank[x]表示x的秩，从x到其某一后代叶节点的最长路径上边的数目
int cmp(const void *a,const void *b)
{
    return ((*(edge*)a).value > (*(edge*)b).value ? 1:-1);
}
/*----------------------并查集的基本操作--------------------------*/
void makeSet()//初始化集合
{
    for(int i=0;i<n;i++)
    {
        father[i]=i;
        rank[i]=0;
    }
}
int findSet(int x)//寻找x所在集合，回溯时压缩路径
{
    if(x!=father[x])
        father[x]=findSet(father[x]);
    return(father[x]);
}
void unionSet(int x,int y)//按秩合并x和y所在的集合
{
    if(rank[x]>rank[y])
        father[y]=x;
    else if(rank[x]<rank[y])
        father[x]=y;
    else 
    {
        rank[y]++;
        father[x]=y;
    }
}
/*-----------------------------主函数-------------------------------*/
void main()
{
    int i,j,x,y,h=0,sum=0,k=0;
    //en表示各个点之间的连接情况，为0表示无边，其他值表示边的权值
    int en[n][n]={{0,4,0,0,0,0,0,8,0},
            {4,0,8,0,0,0,0,11,0},
            {0,8,0,7,0,4,0,0,2},
            {0,0,7,0,9,14,0,0,0},
            {0,0,0,9,0,10,0,0,0},
            {0,0,4,14,10,0,2,0,0},
            {0,0,0,0,0,2,0,1,6},
            {8,11,0,0,0,0,1,0,7},
            {0,0,2,0,0,0,6,7,0}};
    
    for(i=0;i<n;i++)//各个边的初始化
        for(j=i;j<n;j++)
        {
            if(en[i][j]!=0)
            {
                e[k].u=i;
                e[k].v=j;
                e[k].value=en[i][j];
                k++;
            }
        }
    makeSet();//初始化集合
    qsort(e,k,sizeof(struct edge),cmp);//按照边的权值非递减顺序对边进行排序
    for(i=0;i<k;i++)
    {
        x=findSet(e[i].u);//寻找x所在集合的标志点
        y=findSet(e[i].v);//寻找y所在集合的标志点
        if(x!=y)//x和y不属于同一个集合
        {
            unionSet(x,y);//进行x和y所在集合的合并操作
            sum+=e[i].value;//将该边的权值计入总代价
            p[h++]=i;
        }
        else{}
    }
    printf("最小生成树的代价为：%d\n",sum);
    printf("最小生成树的各边及权值依次为：\n");
    for(i=0;i<h;i++)
        printf("边%c - %c 权值:%d \n",e[p[i]].u+'a',e[p[i]].v+'a',e[p[i]].value);
}

2.1 prim算法

　　同kruskal算法一样，prim算法也是通用最小生成树算法的特例，其执行非常类似于寻找图的最短路径的dijkstra算法，树从任意根顶点r开始形成，并逐渐生成，直至覆盖了v中的所有顶点。在每一步中，一条连接了树A与（V,A）中某孤立顶点的轻边被加入到树A中，因此当算法终止时刻，A中的边就形成了一棵最小生成树。具体过程参见：http://ebkk.blog.163.com/blog/static/194135085201159115248724/中所述的流程图

　　（1）采用数据结构书本上的算法实现

/*-------------------------------------------------------------------
 *名称：prim算法的实现
 *作者：lp
 *时间：2012.7.2
 *环境：vc++6.0
 *实现描述：        
 *-------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#define n 9//图中点的个数
#define max n*n//图中的边的个数
#define inf 9999//标示无穷大
struct edge{
    int u;//起点
    int v;//终点
    int value;//边的权值
}e[max];
int p[n];//p[i]用于记录依次加入最小生成树的顶点

/*-----------------------------prim算法-----------------------------*/
int prim(int en[][n],int v)
{
    int i,j,k,kk=0,min=inf,count=0;//min标示无穷大，count用于记录最小生成树各边的权值
    int lowcost[n];//lowcost[i]用于记录顶点i到最小生成树t中的顶点的最短路径权值
    int intree[n];//intree[i]用于记录顶点i是否在最小生成树中，1：在；0：不在。
    for(i=0;i<n;i++)//初始化
    {
        if(en[i][v]==inf)//路径不可达
            lowcost[i]=inf;
        else //有可达路径
            lowcost[i]=en[i][v];
            intree[i]=0;
            p[i]=-1;
    }
    intree[v]=1;//标记顶点v为最小生成树中的顶点
    p[0]=v;
    for(i=0;i<n-1;i++)//选择其余的n-1个顶点
    {
        min=inf;
        for(j=0;j<n;j++)//选出到最小生成树t中顶点最短的顶点k
        {
            if(intree[j]==0 && lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
        }
        count=count+min;//记录权值
        intree[k]=1;
        v=k;
        p[++kk]=k;//记录依次加入最小生成树的顶点
        for(j=0;j<n;j++)
        {
            if(intree[j]==0 && en[v][j]!=0 && en[v][j]<lowcost[j])
                lowcost[j]=en[v][j];
        }
    }
    return(count);
}
/*-----------------------------主函数-------------------------------*/
void main()
{
    int i,sum=0;
    char vex;
    //en表示各个点之间的连接情况，为inf表示无边，其他值表示边的权值看 :）  
    int en[n][n]={{0,4,inf,inf,inf,inf,inf,8,inf},
            {4,0,8,inf,inf,inf,inf,11,inf},
            {inf,8,0,7,inf,4,inf,inf,2},
            {inf,inf,7,0,9,14,inf,inf,inf},
            {inf,inf,inf,9,0,10,inf,inf,inf},
            {inf,inf,4,14,10,0,2,inf,inf},
            {inf,inf,inf,inf,inf,2,0,1,6},
            {8,11,inf,inf,inf,inf,1,0,7},
            {inf,inf,2,inf,inf,inf,6,7,0}};
    printf("输入最小生成树的构造开始顶点(a,b,c,d,e,f,g,h,i):\n");
    scanf("%c",&vex);
    sum=prim(en,vex-'a');
    printf("最小生成树的代价为：%d\n",sum);
    printf("构造最小生成树依次加入树的顶点为：\n");
    for(i=0;i<n-1;i++)
        if(p[i]!=-1)
            printf("%c -> ",p[i]+'a');
        printf("%c\n",p[i]+'a');
}

　　（2）采用最小堆的算法实现

参考：http://lqm1987.blogbus.com/logs/67465589.html

　　

3 参考资料

（1）算法导论

（2）并查集：http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.html

（3）qsort：http://blog.sina.com.cn/s/blog_78b9c0f50100si6b.html

（3）prim算法：http://www.cnblogs.com/hankskfc/archive/2011/09/27/2193559.html