贪心

知识点总结报告

知识点：

贪心之最小生成树

（原理）贪心的基本思路：从当前情况出发根据某个优化目标做最优选择，而不考虑各种可能的整体情况，从而避免了为找最优解要穷尽所有可能的问题求解方法。

在贪心算法中，选取一个量度标准做贪婪处理所得到该量度意义下的最优解并不一定是问题的最优解，可能是次优解。

一、最小生成树的性质

　　设G = (V,E)是连通带权图，U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它意(u,v)为其中一条边。这个性质有时也称为MST性质。

二、Prim算法——普里姆算法

　　设G = (V,E)是连通带权图，V = {1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S = {1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i ∈S,j ∈V – S,且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S = V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

void Prim (MatGraph g,int v)
{    int lowcost[MAXV];
    int MIN;
    int closest[MAXV],i,j,k;
    for(i=0;i<g;i++)                                //给咯我cost[ ]和closest[ ]置初值  
    {    lowcost[i]=g.edges[v][i];
          closest[i]=v;
    }
    for(i=1;i<g.n;i++)                             //找出(n-1)个顶点
    {    MIN=INF;
            for(j=0;j<g.n;j++)                    //在(V-U)中找出离U最近的顶点k
                    if(lowcost[j]!=0&&lowcost[j]<MIN)
                    {    MIN=lowcost[j];
                            k=j;                         //k记录最近顶点的编号
                    }
            printf("边(%d,%d)权为:%d\n",closest[k],k,MIN);    //输出最小生成树的一条边
            lowcost[k]=0;                          //标记k已经加入U
            for(j=0;j<g.n;j++)                  //对(V-U)中的顶点j进行调整
                if(lowcost[j]!=0&&g.edges[k][j]<lowcost[j])
                {    lowcost[j]=g.edges[k][j];
                      closest[j]=k;                //修改数组lowcost和closest
                }
    }
}                                

三、Kruskal算法——克鲁斯卡尔算法

　　当图的边数为e时，Kruskal算法所需的时间是O(eloge)。当e = Ω(n^2)时，Kruskal算法比Prim算法差；但当e = o(n^2)时，Kruskal算法比Prim算法好得多。

给定无向连同带权图G = (V,E),V = {1,2,...,n}。Kruskal算法构造G的最小生成树的基本思想是：

（1）首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小大排序。

（2）从第一条边开始，依边权递增的顺序检查每一条边。并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点是，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看k+1条边。这个过程一个进行到只剩下一个连通分支时为止。

此时，已构成G的一棵最小生成树。

Kruskal算法的选边过程：

1 -> 3 : 1

4 -> 6 : 2

2 -> 5 : 3

3 -> 4 : 4

2 -> 3 : 5

typedef struct
{    int u;                              //边的起始顶点
      int v;                              //边的终止顶点
      int w;                             //边的权值
}Edge;
void Kruskal(MatGraph g)                                  //改进的Kruskal算法
{    int i,j,k,u1,v1,sn1,sn2;
     UFSTree t[MaxSize];
     Edge E[MaxSize];
    k=1;
    for(i=0;i<g.n;i++)                                       //e数组的下标从1开始计
        for(j=0;j<=i;j++)                                   //由g产生的边集数E
            if(g.edges[i][j]!=0&&g.edes[i][j]!=INF)
            {    E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];
                  k++;
            }
    HeapSort(E,g,e);                                       //采用堆排序对E数组按权值递增排序
    MAKE_SET(t,g,n);                                     //初始化并查集数t
    k=1;                                                       //k表示当前构造生成树的第几边，初值为1
    j=1;                                                       //E中边的下标从1开始
    while(k<g.n)                                          //生成的边数小于n时循环
    {    u1=E[j].u;
          v1=E[j].v;                                       //取一条边的头尾顶点编号u1和v2
          sn1=FIND_SET(t,u1);
          sn2=FIND_SET(t,v1);                      //分别得到两个顶点所属的集合编号
          if(sn1!=sn2)                                   //两顶点属于不同的集合，该边是最小生成树的一条边
          {    printf("(%d,%d):%d\n",u1,v1,E[j],w);
                k++;                                        //生成边数增加1
                UNION(t,u1,v1);                       //将u1,v1两个顶点合并
            }
            j++;                                           //扫描下一条边
    }
}