Prim朴素算法 O(n^2)

每次取与连通图相连的最小的权值点,加入到连通图中并且更新其他所有点与这个点最小距离

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n,m;
int g[N][N], dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;                 //t代表：扩展连通图相临边的最小点
        for (int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        if(dist[t] == INF)  return INF;
        st[t] = true;
        res += dist[t];
        for(int j = 1;j <= n;j ++)  //更新一下，剩下结点与连通图的dist
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int res = prim();
    if(res != INF) printf("%d\n",res);
    else    printf("impossible");

    return 0;

}

Kruskal算法: O(mlogm)

贪心策略:先所有边sort,再将所有的点创建并查集树,最后遍历执行并记cnt

直接用三元组存储方式即可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int n,m;

//定义图中的所有边,创建边表
struct Edge
{
    int a, b, c;
    bool operator< (const Edge& t) const
    {
        return c < t.c;
    }
}e[M];

//并查集
int p[N];
//寻找祖结点函数
int find(int x)
{
    if(p[x] != x)   p[x] = find(p[x]);
    return p[x];
}


int main()
{
    scanf("%d %d", &n, &m);
    //初始化edge集合
    for (int i = 0; i < m; i ++ )
        scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].c);
    //对edge集合排序
    sort(e, e + m);
    //将所有图中的点建立并查集树
    for(int i = 1;i <= n;i ++)  p[i] = i;

    int res = 0, cnt = n;
    for(int i = 0;i < m;i ++)
    {
        int a = e[i].a, b = e[i].b, c = e[i].c;
        //判断当前两个点是否在一个连通块
        if(find(a) != find(b))
        {
            res += c;
            cnt --;
            //合并同一个集合
            p[find(a)] = find(b);
        }
    }
    if(cnt > 1) puts("impossible");
    else    printf("%d\n",res);

    return 0;
}

补充:

1. 最小生成树的树可能不一样,但权值和一定一样
2. 从同一个点发出的最小生成树都不一定生成相同的树,不同点更不同
3. 如果一个图中就一颗生成树,那么prim还是kruskal生成结果一样
4. 一个图中最小生成树唯一的条件:当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。