算法基础课笔记（二一）

3.7：最小生成树

参考资料： https://oi-wiki.org/graph/mst/#_2。（有图示）

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

给定一个无向图，在图中选择若干条边把图的所有节点连起来，要求边长之和最小。在图论中，叫做求最小生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

对于最小生成树，稠密图常用朴素版Prim算法，稀疏图常用Kruskal算法，堆优化Prim用的较少。

最小生成树的两种算法都能处理负权和负环。最小生成树中不应该有自环。

不存在最小生成树的情况：点不连通。

对于n个顶点的无向连通图来说，如果最小生成树存在，那么它的边数一定是n-1。

3.7.1：朴素版Prim算法

Prim算法和Dijkstra算法非常像，同样基于贪心思想。Prim可以处理带负权图。

该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。

y总算法基础课讲解视频： https://www.acwing.com/video/25/ 12:13。（很细致）

例题：858. Prim算法求最小生成树（模板题）

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围
1≤n≤500,
1≤m≤10^5,
图中涉及边的边权的绝对值均不超过 10000。

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6

每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。

定义点到集合的距离：当集合外一点有多条边连向集合内的点，取权值最小的边作为点到集合的距离。

若集合外一点没有边连向集合内的点，则定义点到集合的距离为INF。

这里的集合也就是最小生成树的连通块，迭代n次，每次迭代将一个点将入到集合中。

参考题解： https://www.acwing.com/solution/content/38312/。

dist数组存的是点到集合的距离，和Dijkstra不一样，Dijkstra是更新从起始点到当前点的距离。

时间复杂度：O(n^2)。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 510,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
bool s[N];
int d[N];// dist存储其他点到集合S的距离

int prim(){//如果图不连通返回INF, 否则返回res
    memset(d,0x3f,sizeof d);
	// d[1] = 0; 如果加上这一句，后面if判断就不用加if (i && xxx)，直接if (xxx)
    // 详细内容参考考研算法辅导课笔记（九）
    int res = 0;// 存放最小生成树的边权之和
    for (int i = 0;i < n;i ++){// n次循环，每次加入一个距离S最近的点t
        int t = -1; // t暂时取为-1，每轮的t都不一样
        for (int j = 1;j <= n;j ++){// 找到集合外离S最近的点t
            if (!s[j] && (t == -1 || d[t] > d[j])) t = j;
        }
        // 如果第2个及以后的点没有连向集合的边，最小生成树不存在
        if (i && d[t] == INF) return INF;
        if (i) res += d[t];// 第1个点不用，先累加，再更新，否则更新时会将自环加进来
        // 这里加上i的判断是特殊处理集合中第一个点，d[1]显然等于INF，d[1]显然没用，它不是一条树边
        s[t] = true;
        // 用t更新其他点到集合的距离
        for (int j = 1;j <= n;j ++) d[j] = min(d[j],g[t][j]);
    }
    return res;
}

int main(){
    IOS;
    
    memset(g,0x3f,sizeof g);
    cin >> n >> m;
    int u,v,w;
    while (m -- ){
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v],w);// 无向图，处理重边
    }
    int t = prim();
    if (t == INF) cout << "impossible\n";
    else cout << t << '\n';
    return 0;
}

// prim函数的另一种写法，少了2个判断
// 通过 dist[1] = 0 声明了起点为1，后面就不用特判是不是第1个点
int prim(){
    memset(d,0x3f,sizeof d);

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

        if (d[t] == INF) return INF;
        res += d[t];
        s[t] = true;

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

    return res;
}

Prim算法的堆优化与Dijkstra算法的堆优化做法类似，不过不常用。

3.7.2：Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。Prim采用点贪心，Kruskal采用边贪心。

前置知识：并查集，图的存储。

Kruskal 算法的时间瓶颈就是第一步的边权排序O(m*logm)。（快排的常数比较小）

关于并查集的部分可以参照连通块中点的数量这道题。

例题：859. Kruskal算法求最小生成树（模板题）

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围
1≤n≤10^5,
1≤m≤2∗10^5,
图中涉及边的边权的绝对值均不超过 1000。

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 1e5+5,M = 2e5+5;
int n,m;
int p[N];

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

struct Edge{
    int a,b,w;// 需要对边排序，用结构体存储
    bool operator< (const Edge& W) const{
        return w < W.w;// 重载小于号
    }
}edge[M];

void kruskal(){
    sort(edge + 1,edge + m + 1);// 数组从下标为1开始存边，注意sort参数
    for (int i = 1; i <= n; i ++ ) p[i] = i;// 初始化并查集
    
    int res = 0,cnt = 0;// res存放最小生成树的边权之和，cnt存放最小生成树的边数
    for (int i = 1;i <= m;i ++){
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        a = find(a),b = find(b);
        if (a != b){
            p[a] = b;
            res += w;
            cnt ++;
        }// n个点一共n-1条边
        if (cnt == n-1) break;// 处理完提前退出
    }
    if (cnt < n-1) cout << "impossible\n";
    else cout << res << '\n';
}

int main(){
    IOS;
    
    cin >> n >> m;
    int u,v,w;
    for (int i = 1; i <= m; i ++ ){
        cin >> u >> v >> w;
        edge[i] = {u,v,w};
    }
    
    kruskal();
    return 0;
}

如何用Kruskal算法求出最小生成树的每条边？

维护一个path数组，当最小生成树需要加边时，path数组记录这条边在edge数组中的编号。