最小生成树

最小生成树

概念

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

Prim算法

Prim算法生成最小生成树的过程基于贪心思想，每次将距离已经连通部分最近的点和对应的边加入连通部分，使得连通部分逐渐扩大，最后将整个图连接起来并且边长之和最小。

Prim（朴素版）

适用于稠密图，时间复杂度为\(O(n^2)\)

先把所有距离初始化为正无穷
for i ： 0～n
	t = 集合S外距离最近的点
	//**与Dijkstra算法不同的地方**
	//Dijkstra算法是用t更新其他点到 起点 的距离
	用 t 更新其他点到 集合 的距离

例如，当b、c、d都被加入到集合s中时，a此时到集合的距离表示为\(min(d1, d2, d3)\)

如果与a相连的点都没有被加入到集合s中，那么a此时到集合的距离表示为\(+∞\)

对于上图，Prim算法的过程为

1）先加入1号点

2）用1号点来更新与之相连的其他点

dis[2] = 1, dis[3] = 2, dis[4] = 7;

3）从当前dis[]数组中找到距离最小的点，也就是2，因此加入2号点到集合中，同时连边1——2

4）用2号点来更新与之相连的其他点（无更优值则无更新）

5）加入3号点到集合中，同时连边1——3

6）用3号点来更新与之相连的其他点

dis[4] = 3

7）加入3号点到集合中，同时连边3——4

8）连了\(n-1\)条边，程序结束

对应的最小生成树：

代码实现

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5005;
int ans = 0;
int n, m;
int g[N][N], dist[N];
//flag数组表示当前点是否被加入到集合s中
bool flag[N];

void prim(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    flag[1] = 1;
    //t代表当前加入的结点
    int t = 1;
    int cs = n-1;
    while(cs--){
        //用t更新其他点到集合的距离
        for(int i = 1; i <= n; i++)
            if(!flag[i] && g[t][i] && dist[i] > g[t][i])    dist[i] = g[t][i];
        //选择距离集合最近的点加入到集合中，并且连边
        int minn = 0x3f3f3f3f, idx = 0;
        for(int i = 1; i <= n; i++){
            if(!flag[i] && minn > dist[i]){
                idx = i;
                minn = dist[i];
            }
        }
        if(minn == 0x3f3f3f3f){
            cout << "orz" << endl;
            return;
        }
        flag[idx] = 1;
        t = idx;
        ans += minn;
    }
    cout << ans << endl;
}

int main(){
    int x, y, z;
    cin >> n >> m;
    while(m --){
        cin >> x >> y >> z;
        if(!g[x][y]){
            g[x][y] = z;
            g[y][x] = z;
        }
        else{
            if(g[x][y] > z){
                g[x][y] = z;
                g[y][x] = z;
            }
        }
    }
    prim();
    return 0;
}

Prim（堆优化版）

适用于稀疏图（但是不常用，通常稀疏图更加倾向用Kruskal算法），时间复杂度为\(O(mlogn)\)

Kruskal算法

时间复杂度为\(O(mlogm)\)

算法思路

1. 按照边的权值将边进行升序排序；\(O(mlogm)\)
2. 从小到大枚举每条边，如果这个边与之前选择的所有边不会组成回路（边a——b，a和b如果是不连通的），就把这条边加入到集合s中；\(O(m)\)
3. 不断判断，直到具有n个顶点的联通网筛选出来n-1条边为止。

此时筛选出来的边和所有的顶点构成此连通网的最小生成树。

对于判断是否会产生回路，我们使用并查集。

• 在初始状态下，各个顶点在不同的集合中
• 遍历每条边的时候，判断该边的两个顶点是否在一个集合中
• 如果边上的这两个顶点在一个集合中，说明两个顶点一定已经连通，那么这条边加上去一定导致环，所以舍去该边。反之如果不在一个集合中，就加入这条边。

代码实现

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005, M = 200005;
int fa[N];
struct Edge{
    int u, v, w;
}edge[M];

bool cmp(Edge a, Edge b){
    return a.w < b.w;
}

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

int main(){
    int n, m, ans = 0;
    int u, v, w;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)     fa[i] = i;
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        edge[i].u = u;
        edge[i].v = v;
        edge[i].w = w;
    }
    sort(edge+1, edge+m+1, cmp);
    int cnt = 0;
    for(int i = 1; i <= m && cnt < n-1; i++){
        //如果边连接的两个点是不连通的
        if(find(edge[i].u) != find(edge[i].v)){
            fa[find(edge[i].u)] = find(edge[i].v);
            ans += edge[i].w;
            cnt ++;
        }
    }
    if(cnt == n-1)      cout << ans << endl;
    else    cout << "impossible" << endl;
    return 0;
}