复习一下最小生成树

最小生成树是什么

在一个连通无向带权图中，最小生成树是指

一个子图，它是一棵树（无环、连通）
包含原图的所有顶点
所有边的权重之和最小

Prim

加点法

从任意一个顶点开始，每次选择一条连接已选顶点集和未选顶点集的最小权边，并将该边连接的顶点加入已选集。逐步扩张，直到包含所有顶点。

算法步骤

随机选择一个起始顶点，加入集合 $U$ （已选顶点集）。
在所有连接 $U$ 内顶点和 $U$ 外顶点的边中，选择一条权重最小的边 $(u, v)$ （其中 $u$ 在 $U$ 中， $v$ 不在 $U$ 中）。
将顶点 $v$ 加入集合 $U$ ，边 $(u, v)$ 加入最小生成树。
重复步骤2、3，直到 $U$ 包含所有顶点。

时间复杂度

使用邻接表 + 二叉堆 $O(E log V)$
使用斐波那契堆可优化至 $O(E + V log V)$

code

cpp

void prim(){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()&&cnt<n){
        int d=q.top().first,u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        sum+=d;
        cnt++;
        for(int i=head[u];i;i=E[i].nxt){
            int v=E[i].to,w=E[i].w;
            if(w<dis[v]) dis[v]=w,q.push({w,v});
        }
    }
}

例子

text

     2
 A ----- B
 |      |
3|      |1
 |      |
 C ----- D
     4

从A开始

选边 (A,B,2)，加入 B
选边 (B,D,1)，加入 D
选边 (A,C,3)，加入 C MST总权重 $2 + 1 + 3 = 6$

Kruskal

加边法

将所有边按权重从小到大排序，每次选择一条最小的边，如果加入这条边不会形成环，就将其加入生成树。

算法步骤

将图中所有边按权重从小到大排序。
初始化一个空的最小生成树。
按权重从小到大遍历每条边（如果当前边连接的两个顶点不在同一个连通分量中（即加入后不会形成环），则将该边加入生成树，并合并这两个连通分量）
直到生成树中有 $V-1$ 条边为止。

实现关键

使用并查集数据结构来高效地判断是否形成环（即检查两个顶点是否属于同一集合）。
需要对所有边进行排序。

时间复杂度

排序边 $O(E log E)$
并查集操作（路径压缩+按秩合并）近似 $O(α(V))$ ，几乎为常数
总复杂度 $O(E log E)$ 或 $O(E log V)$ （因为E最多为V²）

code

cpp

int fa[N],n,m;       //用来实现并查集，记录每个顶点的祖宗顶点
struct Edge{
    int a,b,w;
    friend bool operator < (Edge a,Edge b){
        return a.w<b.w;
    }
}E[M];
int find(int u){//寻找祖宗顶点，并且路径压缩
    if(u==p[u]) return u;
    return p[u]=find(p[u]);
}
int kruskal(){
    sort(E,E+m);        //将边按照边权大小排序
    iota(fa+1,fa+n+1,1);//对fa[]数组初始化，一开始每个顶点的祖宗都是自己
    int sum=0,cnt=0;      //记录最后的答案，即最小生成树的所有边的边权;记录连通部分有多少边，方便最后判断图是否连通
    for(int i=0;i<m;i++){//遍历每一条边
        int a=E[i].a,b=E[i].b,w=E[i].w;
        a=find(a),b=find(b);        //找到边的两个顶点的祖宗（看俩个顶点是否属于一个集合）
        if(a!=b){//如果祖宗不同，也就是不在一个集合
            sum+=w;
            cnt++;      //连通部分的边数加一
            p[a]=b;     //把a的祖宗置为b
        }
    }
    if(cnt<n-1) return 0x3f3f3f3f;//如果最后连通部分的边数小于n-1，就说明图不连通
    else return res;
}

例子

text

     2
 A ----- B
 |      |
3|      |1
 |      |
 C ----- D
     4

边排序后(B,D,1), (A,B,2), (A,C,3), (C,D,4)

选(B,D,1)，无环，加入
选(A,B,2)，无环，加入
选(A,C,3)，无环，加入
已选3条边（V=4，边数已够），停止。MST总权重 $1+2+3=6$

对比

特性	Prim算法	Kruskal算法
核心思想	加点（从一点开始扩张）	加边（按权重从小到大选）
数据结构	优先队列	并查集、需排序所有边
时间复杂度	$O(E log V)$	$O(E log E)$
适用图	稠密图（边多顶点少）	稀疏图（边少顶点多）
过程特点	始终维护一棵连通的树	中间过程可能是多棵树的森林
起始点	需要指定一个起始点	不需要起始点，全局考虑边

评论