【极简数据结构14】——最小生成树

所谓的最小生成树，就是给你一个连通图，你需要求出其极小连通子图：图中的每个点都需要包含在内，且整体的权值尽可能的小。和最短路径的区别是：最小生成树保证整个拓扑图的权值之和为最小，但不保证两点之间的距离最小。

一般有两种算法来解决这类问题：Prim算法和Kruskal算法，它们都是基于贪心算法实现的，不同的是，Prim算法从顶点入手，寻找最小边。而Kruskal是直接从边入手，将边(edge)进行排序之后，通过判断是否成环来进行挑选。直接来看动画演示吧。

Prim算法

最开始时，存储最小生成树（MST）的集合中没有元素，而另一个集合表示不在MST中的点，在算法运行的过程中，MST集合会越来越大，而另一个集合会越来越小，最终只存在MST集合，即为最终的答案。算法详细过程如下：

题目链接：https://www.acwing.com/problem/content/860/

#include<iostream>
#include<cstring>
using namespace std;

const int N = 550;
int dist[N];
bool vis[N];
int n, m;
int map[N][N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    
    int res = 0;
    for(int i = 0; i < n; ++i) {
        int t = -1;
        for(int j = 1; j <= n; ++j) {
            if(!vis[j] && (t == -1 || dist[j] < dist[t])) {   //寻找最短的边
                t = j;
            }
        }
        
        if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;   //如果不是第一条边且不连通，那说明构不成最小生成树
        
        if(i) res += dist[t];    //只要不是第一条边，那么就可以加到res中
        vis[t] =  true;        //设置为访问过
        for(int j = 1; j <= n; ++j)  //使用当前的边去更新其他边
            dist[j] = min(dist[j], map[t][j]);
    }
    
    return res;
}

int main() {
    memset(map, 0x3f, sizeof map);
    cin >> n >> m;
    while(m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        map[a][b] = map[b][a] = min(map[a][b], c);
    }
    
    int t = prim();
    
    if(t == 0x3f3f3f3f) cout <<"impossible" << endl;
    else cout << t << endl;   
    
    return 0;
}

Kruskal算法

将边的权值进行从小到大排序之后，首先考虑权值小的边，如果这条边和当前以选顶点不构成环，则说明可以选。所以我们现在只需要考虑如果判断构成环就行了。我之前讲过一个数据结构就是专门来判断这类问题的，直接用并查集维护就行了。

详细的算法过程：

题目链接：https://www.acwing.com/problem/content/861/

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
const int M = 2e6 + 10;

struct edge {
    int x, y, w;
    bool operator < (const edge & W) const {
        return w < W.w;
    }
} edges[M];

int fa[N];
int n, m;

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

int kruskal() {
    sort(edges, edges + m);  //对边进行排序
    for(int i = 1; i <= n; ++i) fa[i] = i;  //初始化并查集
    
    int ans = 0, cnt = 0;
    for(int i = 0; i < m; ++i) {  //对于每条边
        int a = edges[i].x, b = edges[i].y, c = edges[i]. w;
        a = find(a), b = find(b);  
        if(a != b) {    //如果a和b不在同一个集合中，那说明没环，所以可以把他们放在一个集合中
            fa[a] = b;
            ans += c;    //答案加上权值
            cnt ++;      //节点个数加加
        }        
    }
    
    if(cnt < n - 1) return 0x3f3f3f3f;  //当前的点不够，说明有的点被孤立了，所以不能构成一颗树
        return ans;
}

int main() {
    cin >> n >> m;
    
    for(int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    
    int t = kruskal();
    if(t == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << t << endl;
    
    return 0;
}

个人觉得kruskal比prim要稍微简单一点，所以kruskal可以重点学习一下。