学步园

Kruskal算法实际上是 贪心＋并查集的结合，只要会了并查集，那么这个算法一点难度都没有了，，，

下来是讲解下这个算法的具体实现步骤和时间复杂度，，首先，对于一个具有ｎ个顶点的图，我们知道至少会有ｎ－１条边，使这个图不构成回路，好了，那么这ｎ－１条边刚好可以构成一棵树，既然要求造价最小的一棵树，那么我们就利用贪心的思想，先对每一条边的权值进行从小到大排序，然后，依次从小到大开始选边，选出来的边在这支离破碎的ｎ个顶点上进行树的构建，如果我们在连边的过程中遇到了两个顶点同属于一个集合的情况，那么我们就利用并查集来预先判定，，让这种情况尽量不要发生，，，通过MlogM的时间，我们就可以构成这棵最小生成树了。。

代码：

# include<cstdio>
# include<iostream>
# include<algorithm>
# include<cstring>
# include<string>
# include<cmath>
# include<queue>
# include<stack>
# include<set>
# include<map>

using namespace std;

# define inf 999999999
# define MAX 2333

int f[10];
int n,m;
int ans;
int cnt;

struct edge
{
    int u;
    int v;
    int w;
}e[MAX];

int cmp ( edge a,edge b )
{
    return a.w < b.w;
}

int getf( int v )
{
    if ( f[v]==v )
        return v;
    else
    {
        f[v] = getf( f[v] );
        return f[v];
    }
}

int merge ( int v,int u )
{
    int t1 = getf(v);
    int t2 = getf(u);
    if ( t1!=t2 )
    {
        f[t2] = t1;
        return 1;
    }
    return 0;
}


int main(void)
{
    cin>>n>>m;
    for ( int i = 1;i <= m;i++ )
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+1+m,cmp);
   
    for ( int i = 1;i <= n;i++ )
    {
        f[i] = i;
    }

    for ( int i = 1;i <= m;i++ )
    {
        if ( merge( e[i].u , e[i].v ) )
        {
            cnt++;
            ans+=e[i].w;
        }
        if ( cnt == n-1 )
        {
            break;
        }
    }

    cout<<ans<<endl;

	return 0;
}