Kruskal算法-最小生成树

2017-07-26  10:32:07

writer：pprp

Kruskal算法是根据边的加权值以递增的方式，一次找出加权值最低的边来建最小生成树；并且每次添加的边不能造成生成树有回路，直到找到N-1个边为止；

适用范围：边集比较少的时候，可以考虑用这个方法；

做法：将图形中所有的边的权值，递增排序（快速排序），按从小到大，依次将邻接边加入到生成树中，加入的生成树不能有回路，直到N-1个边；

还用到了并查集；

---

代码如下：

#include <iostream>

using namespace std;

const int MAXN = ;

const int INF = ;

int n,e;// n是点的数量，e是边的数量

int x[MAXN],y[MAXN],w[MAXN];

int parent[MAXN];

int Find(int x)

{

    if(parent[x] == x)

        return x;

    else

        return parent[x] = Find(parent[x]);

}

void Merge(int a,int b)

{

    int pa = Find(a);

    int pb = Find(b);

    if(pb < pa)

        swap(pb,pa);

    if(pa!=pb)

        parent[pa] = pb;

}

void kruskal()

{

    int i,p,ans;  //p是已经加入的边数,ans是加入边的边权之和

    for(i = ; i<=n ; i++) //initialize

    {

        parent[i] = i;

    }

    p = ;

    ans = ;

    for(i = ; i <= e; i++)

    {

        if(Find(x[i])!=Find(y[i]))// 两点没有在同一个集合中,归并两个集合

        {

            ans += w[i];

            Merge(x[i],y[i]);

            p++;

            if(p == n)    //这里不是n-1，因为初始化的时候,p = 1

            {

                cout << ans << endl;

                return;

            }

        }

    }

    return;

}

void sort(int i, int j)

{

    if(i >=j)

        return;

    int m,n,k;

    m = i;

    n = j;

    k = w[(i+j)>>];

    while(m <= n)

    {

        while(w[m]<k)

            m++;

        while(w[n]>k)

            n--;

        if(m <= n)

        {

            swap(x[m],x[n]);

            swap(y[m],y[n]);

            swap(w[m],w[n]);

            m++;

            n--;

        }

    }

    sort(i,n);

    sort(m,j);

}

int main()

{

    int i,j;

    cin >> n >> e;

    for(i = ; i <= e ; i++)

    {

        cin >> x[i] >> y[i] >> w[i];

    }

    sort(,e);

    kruskal();

    return ;

}

这个sort函数比较有特点，sort函数根据权值w[MAXN]的大小进行判断，交换的时候将x[MAXN],y[MAXN]都交换了，相当于将 x,y,w对应起来；

图例描述：参考：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

首先第一步，我们有一张图Graph，有若干点和边

将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了右图

在剩下的变中寻找。我们找到了CE。这里边的权重也是5

依次类推我们找到了6,7,7，即DF，AB，BE。

下面继续选择， BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。

最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是右：