最小生成树

常用：

稠密图使用朴素版 prim算法，时间复杂度O(n ^ 2)

稀疏图使用kruskal算法，时间复杂度O(m * log m)

不常用的堆优化prim算法:

稀疏图使用堆优化版本的prim算法， 时间复杂度O(m * logn)

prim算法代码实现：

int prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    int res = 0;
    for(int i = 0 ; i < n ; i++)
    {
        int t = -1;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!choose[j] && (t == -1  || dist[j] < dist[t]))
            {
                t = j;
            }
        }

        choose[t] = 1;
        if(dist[t] == 0x3f3f3f3f)
        {
            return dist[t];
        }
        res += dist[t];
        for(int k = 1 ; k <= n ; k++)
        {
            dist[k] = min(dist[k],g[t][k]);
        }
    }
    return res;
}

kruskal算法代码实现：

struct edg
{
    int a,b,w;
}edgs[N];

int p[N];

int n,m;

int cmp(struct edg temp1 , struct edg temp2)
{
    return temp1.w < temp2.w;
}

int find(int x)
{
    if(p[x] != x)
    {
        p[x] = find(p[x]);
    }
    return p[x];
}

int main()
{
    scanf("%d %d",&n,&m);

    for(int i = 1 ; i <= n ; i++)
    {
        p[i] = i;
    }
    for(int i = 0 ; i < m ; i++)
    {
        scanf("%d %d %d",&edgs[i].a,&edgs[i].b,&edgs[i].w);
    }


    sort(edgs,edgs + m , cmp);

    int res = 0;
    int cnt = 0;

    for(int i = 0 ; i < m ; i++)
    {
        int first = edgs[i].a;
        first = find(first);
        int second = edgs[i].b;
        second = find(second);
        int wei  = edgs[i].w;
        if(first != second)
        {
            p[first] = second;
            res += wei;
            cnt++;
        }
    }
    if(cnt != n - 1)
    {
        printf("impossible\n");
    }
    else
    {
        printf("%d\n",res);
    }

    return 0;
}