最小生成树

生成树定义：是原图的一个极小连通子图，含有原图的全部顶点，但只有n-1条边。它连通但边只有n-1，也就是说任意让两点连边必定成环，不过这结论好像没啥用。

最小生成树：对于一张图的生成树可能有多种，对于边权和最小的一种就是最小生成树了。

 

prim算法

 

首先首先，我们来几个标识，原图是N={V,E}，TE是N上最小生成树的边集，然后有个已选点集合U，那么未选点集就是V-U了。

首先，先来个起点，加入到U里面。

然后，在所以边（a，b），a属于U，b属于V-U里面，找一条权值最小的边（a₀，b₀），并入集合TE，同时b₀加入到U。

 

最终，经过不断的重复，U越来越多，达到n个点，也就是说U=V；

 

证明：    设prim生成的图为G₀；

　　　　假设存在G_min使得cost(G_min)<cost(G₀),则G_min存在边<u,v>不属于G₀;

　　　　将<u,v>加入G_mink可以得到一个环，且<u,v>不是该环的最长边

　　　　这与prim每次生成最短边矛盾；

prim的实现：

　　首先会用到closedge结构体数组，包括adjvex域和lowcost域；

 

struct node{
    int adjvex;
    int lowcost;
}closedge[maxn];   //closedge[i]中，i和closedge[i].adjvex组成一条边，权值为lowcost
//整个数组用于记录U到V-U具最小权值的边，每次选最小的就是上面的步骤二了

 先来看看算法分析：

struct node{
    int adjvex;
    int lowcost;//一开始初始化为正无穷
}closedge[maxn];   //closedge[i]中，i和closedge[i].adjvex组成一条边，权值为lowcost
//整个数组用于记录U到V-U具最小权值的边，每次选最小的就是上面的步骤二了

void prim(AMGRAPH G, char u)
{//以名字u为起点，在邻接矩阵表示的图G中，构建最小生成树
    int k=locate(G,u);//寻找u名字在定点表中的下标
    for(int i=0;i<n;i++)
        if(i!=k) closedge[i]={u,G.arc[k][j]};//对起点的邻接点初始化
    closedge[k].lowcost =0;//为0就代表着选过了
    for(int i=1;i<G.vexnum;i++)
    {//选择其余n-1个点
        k=min(closedge);//找出closedge中lowcost最小的编号（下标）
        int u0=closedge[k].adjvex;//属于U
        int v0=G.vexs[k];         //属于V-U
        cout<<u0<<v0;
        closedge[k].lowcost =0;
        for(int j=0;j<G.vexnum;++j){
            if(G.arc[k][j]<closedge[j].lowcost )
                closedge[j].lowcost=G.arc[k][j];
                closedge[j].adjvex =G.vex[k];
        }
    }
}

正式代码：

 1 struct node{
 2     int adjvex; /*或者*/ char adjvex;//一个是编号一个是名字
 3     int lowcost;//一开始初始化为正无穷
 4 }closedge[maxn];   //closedge[i]中，i和closedge[i].adjvex组成一条边，权值为lowcost
 5 //整个数组用于记录U到V-U具最小权值的边，每次选最小的就是上面的步骤二了
 6 
 7 int locate(AMGRAPH G,char u)
 8 {
 9     for(int i=0;i<=n;i++)
10         if(G.vexs[i]==u)
11             return i;
12 }
13 
14 void prim(AMGRAPH G, char u)
15 {//以名字u为起点，在邻接矩阵表示的图G中，构建最小生成树
16 
17     int k=locate(G,u);//寻找u名字在定点表中的下标
18     for(int i=0;i<n;i++)
19         if(i!=k) closedge[i]={u,G.arc[k][j]};//对起点的邻接点初始化
20     closedge[k].lowcost =0;//为0就代表着选过了
21     
22     for(int i=1;i<G.vexnum;i++)
23     {//选择其余n-1个点
24     
25         int temp=INT-MAX,k;
26         for(int j=0;j<G.vexnum;j++)
27         {
28             if(closedge[j].lowcost<temp&&closedge[j].lowcost!=0)//对于未选的最小权值的点
29                 k=j;
30         }
31         
32         char u0=closedge[k].adjvex;//属于U
33         char v0=G.vexs[k];         //属于V-U
34         cout<<u0<<v0;
35         
36         closedge[k].lowcost =0;//标记k，代表选了
37         
38         for(int j=0;j<G.vexnum;++j){//刷新与k的邻接点，若权值比lowcost小，就刷新
39             if(G.arc[k][j]<closedge[j].lowcost )
40                 closedge[j].lowcost=G.arc[k][j];
41                 closedge[j].adjvex =G.vex[k];
42         }
43     }
44 }

View Code

 好啦，这算是彻底领悟了，那就看看更简单的克鲁斯卡尔算法；

克鲁斯卡尔

 与prim不同，kruskal是加边

与课本不同，这是另一种描述，很像哈夫曼树

 

克鲁斯卡尔算法：先构造一个只含n个顶点，但边集为空的子图，

　　　　　　　　把子图中各个顶点看成各棵树的根节点，之后，

　　　　　　　　从边集选权值最小的边，若该边的两个顶点属于不同的树

　　　　　　　　就加进子图，把两棵树并成一颗，以此类推，直至森林中只有一棵树。

这个定义本质还是不断让两个连通分量变成一个，知道子图连通。

 

证明：这这这显而易见啊，不过还是要证的，网上的术语好烦，这里以后补。

 

那么如何判断一条边连的是不是两个不同的连通分量呢？

如果是同一连通分量，那么加入这条边就一定成环，我们可以判断它成不成环，

或者直接判断属不属于同一个连通分量，答案呼之欲出——并查集

代码：

 

 1 struct node{
 2     int u,v,w;
 3 }map[maxn];
 4 
 5 bool cmp(node a,node b)
 6 {
 7     return a.w <b.w ;
 8 }
 9 
10 int find(int x)
11 {
12     return x==p[x]?x:p[x]=find(p[x]);//并查集，一直找掌门，并将中间赋值
13 }
14 
15 void kelusikaer (node map[] ,int u)
16 {//对图map图，计算最小生成树的边权和
17     int p[maxn];
18     for(int i=0;i<n;i++)
19         p[i]=i;
20     /*这里输入数据*/
21     sort(map,map+k,cmp);//k为边的数目
22     int ans=0;
23     for(int i=0;i<k;i++)
24     {
25         int x=find(map[i].u );
26         int y=find(map[i].v );
27         if(x!=y){//如果不等，就代表不是同一个连通分量
28             ans+=map[i].w ;
29             p[x]=y;//代表合并了两个连通分量
30         }
31     }
32     cout<<ans<<endl;
33 }

View Code