一、 最小生成树知识框架

1.稠密图最小生成树

1.1 稠密图用朴素的 prim 算法

Step1: 初始化 dst[i] = 0x3f3f3f3f
Step2: n次迭代，每轮迭代确定一个新的节点（最小生成树节点）
找出一个不在 s(已确定最小生成树集合节点)中距离最近的节点 t
把 t加入到 s中
用 t更新其他所有点到集合(最小生成树集合)的距离

代码模板

时间复杂度O(n^2)

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dst[N];
int vst[N];

int prim()
{
    memset(dst, 0x3f, sizeof dst);

    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(vst[j] == false && (t==-1 || dst[j] < dst[t]))
            {
                t = j;
            }
        }
        //cout << i << " " << "t=" << t << " " << dst[t] << endl;

        if(t > 1 && dst[t] == INF) return INF;
        if(t > 1) res += dst[t];
        vst[t] = true;

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

    return res;
}

2.稀疏图最小生成树

2.1 稀疏图用kruskal算法

Step1: 对所有边排序
Step2: 从小到大依次处理每一条边，如果 a、b所在的边 w 不在同一个集合当中，则加入同一个集合；如果在同一个集合当中，则跳过
这一步用并查集做

代码模板

时间复杂度O(mlogm)

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

int kruskal()
{
    sort(edges, edges + m);

    for(int i = 0; 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;
        int pa = find(a), pb = find(b);
        if(pa != pb)
        {
            p[pa] = pb;
            cnt++;
            res += w;
        }
    }

    if(cnt != n - 1) return -1; // 如果所有的边处理完之后，最小生成树的边不等于 `n-1`，说明不联通
    else return res;
}