最小生成树问题

两种最小生成树的解决方法

1、Prim算法：

时间复杂度：

​ 稠密图 O(n^2）

​ （1）朴素版： O(n^2) —– 邻接矩阵
​ （2）堆优化版：被kruskal完爆（×）

核心思路：

​ 先从某一个点开始，逐渐把所有点与该点连接起来，每次连通的时候，我们是选择当前这个
​ 点所在的连通块，与外面连的所有边里，选择一条最短的一条边加入连通块中。每次扩展一个
​ 点进来，扩展n - 1次即可。

代码模板：

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

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

        if (dist[t] == INF) return INF;
        res += dist[t];

        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], g[t][j]);

        st[t] = true;   //表示这个点已经加入集合
    }

    return res;
}

2、Kruskal算法：

时间复杂度：

​ 稀疏图 并查集 + 快排

核心思路：

​ 基于并查集，先将所有边从小到大排序，每一次从小到大枚举所有边，当枚举到某一条边时，
​ 左边的一个点一定在某个连通块中，右边的点也一定在某一个连通块中，当前枚举的这条边
​ 可以分为几种情况：
​ （1）当前这条边连接的两个点已经连通了，那么就不用连接
​ （2）当前这条边连接的两个点不连通，那么久把这条边加到生成树中。
​ 维护连通性可以用并查集。
​ 直接用结构体存下：a, b, w。

代码模板：

struct Edge	//定义结构体和重载小于号
{
    int a, b, w;

    bool operator < (const Edge &W) 
    {
        return w < W.w;
    }
}edges[M];

int find(int x)	//并查集模板
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()	//kruskal模板
{
    sort(edges, edges + m); //将所有边的权值相加

    for (int i = 1; i <= n; i ++) p[i] = i; //初始化并查集

    int res = 0, cnt = 0;

    for (int i = 0; i < m; i ++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        if (find(a) != find(b)) //判断两个点是否在同一个集合里，
        {
            p[find(a)] = find(b);   //将两个点连上一条线
            res += w;   //累加集合的权重
            cnt ++;     //每加入一条边到集合里，就累加一次
        }
    }
    if (cnt < n - 1) return INF;    //如果加入集合的次数，小于点的个数减一（n个点需要n-1条边连通），说明不连通
    return res;
}