【MIX】最小生成树(1) Prim算法

5208

2020.06.20

2020.06.23

发布于未知归属地

基本概念
时间复杂度
相关例题
1. ACW: 最短网络
2. 洛谷: Watering the Field S
生成树
参考文献

基本概念

Prim算法是用于生成无向带权连通图的最小生成树(MST)的一种算法, 并且可以解决边权值为负的情况. Prim算法从任意一顶点 $x$ 开始, 初始化 $V^{'} = x$ , 每次采取贪心策略(与Dijkstra算法思想一致)选取跨越 $V$ 与 $V - V^{'}$ 的最小边, 扩大现有的子树 $V^{'}$ , 直到遍历了图中所有的顶点.

算法正确性证明

设 $G = (V, E)$ 是一个带权连通无向图, $T$ 为构成最小代价的生成树的边集合, 顶点集合 $V$ , $U$ 为 $V$ 中构成MST的顶点集合. 如果边 $(u, v)$ 具有最下代价, 且 $u \in U$ , $v \in V - U$ , 则MST包含边 $(u, v)$ , 将 $v$ 加到 $U$ 中, $(u, v)$ 加入到 $T$ 中, 循环 $∣ V ∣$ 次后到达 $U = V$ .
Lemma 1 如果边 $(u, v)$ 具有最小代价, 且 $u \in U$ , $v \in V - U$ , 则 $G$ 中包含 $T$ 的最小代价生成树一定包含 $(u, v)$ .

可以使用反证法证明Lemma 1.
假设 $G$ 中任何一棵包含 $T$ 的MST都不包含 $(u, v)$ , 设该MST为 $T^{'}$ , 由MST的性质可以知道, $T^{'}$ 为连通的, 因此从 $u$ 到 $v$ 必定存在一条路径 $(u^{'}, v^{'})$ , 且满足 $u^{'} \in U$ , $v^{'} \in V$ , 考虑使用边 $(u, v)$ 代替 $(u^{'}, v^{'})$ 得到生成树为 $\overset{ˉ}{T}$ , 由于 $(u, v)$ 具有最小代价, 因此替换后的树 $\overset{ˉ}{T}$ 相比较 $T^{'}$ 具有更小的权值和, 与 $T^{'}$ 是MST的性质矛盾. $□$

根据Lemma 1可以知道, 在Prim算法的每一步中加入的边都会出现在最终的MST中, 因此认为该贪心策略是正确的.

算法流程

从以上分析可以知道, Prim算法与Dijkstra算法的求解思路一致, 但是在Dijkstra算法中, dist数组维护了当前顶点到源点node的最短距离; 而在Prim算法中, dist维护了当前顶点到当前生成树的距离.

初始化dist数组为INF, 访问数组vis为false.
选定任意一个节点node, 标记vis[node]=true, dist[node]=0
找出所有未访问过的点中的距离最小的点u, 标记vis[u]=true, 将最后一次松弛的边加入生成树
以u作为中间点, 访问其所有邻边进行松弛, 被松弛的点v记录下(u,v)边
循环 $∣ V ∣ - 1$ 次

算法模板

/*
使用邻接矩阵g[N][N]存储图
*/
void prim(){
    memset(vis, 0x00, sizeof vis);
    for(int i=1; i<=n; ++i) dist[i]=INF;
    dist[1]=0;
    int ans=0;
    for(int i=1; i<=n; ++i){
        int node=-1;
        for(int j=1; j<=n; ++j){
            if(!vis[j] && (node==-1 || dist[j]>dist[node])) node=j;
        }
        if(node==-1) break;
        vis[node]=true;
        ans+=dist[node];
        for(int j=1; j<=n; ++j) dist[j]=min(dist[j], g[node][j]);
    }
}

时间复杂度

Prim算法循环 $∣ V ∣ - 1$ 次, 使用线性扫描算法寻找最小值的时间复杂度为 $O (∣ V ∣^{2} + ∣ E ∣)$ , 使用堆优化版Prim算法的时间复杂度是 $O (∣ E ∣ l o g ∣ V ∣)$ .

相关例题

ACW: 最短网络

线性扫描Prim算法代码如下

#include <bits/stdc++.h>
using namespace std;

const int N=105;
int n;
int g[N][N];
bool vis[N];
int dist[N];

int prim(){
    dist[1]=0;
    int ans=0;
    for(int i=0; i<n; ++i){
        int node=-1;
        for(int j=1; j<=n; ++j)
            if(!vis[j] && (node==-1 || dist[j]<dist[node])) node=j;
        if(node==-1) break;
        vis[node]=true;
        ans+=dist[node];
        
        // update adj nodes
        for(int j=1; j<=n; ++j) dist[j]=min(dist[j], g[node][j]);
    }
    return ans;
}

int main(){
    memset(vis, 0x00, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    cin>>n;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            cin>>g[i][j];
            
    cout<<prim()<<endl;
    
    return 0;
}

堆优化版Prim算法代码如下

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
#define fi first
#define se second

const int N=105;
int n;
int g[N][N];
bool vis[N];
int dist[N];

int prim(){
    priority_queue<PII, vector<PII>, greater<PII>> q;
    int ans=0;
    dist[1]=0;
    q.push({dist[1], 1});
    while(!q.empty()){
        int node=q.top().se;
        q.pop();
        if(vis[node]) continue;
        vis[node]=true;
        ans+=dist[node];
        for(int i=1; i<=n; ++i){
            if(dist[i]>g[node][i]){
                dist[i]=g[node][i];
                q.push({dist[i], i});
            }
        }
    }
    return ans;
}

int main(){
    memset(vis, 0x00, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    cin>>n;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            cin>>g[i][j];
            
    cout<<prim()<<endl;
    
    return 0;
}

洛谷: Watering the Field S

转换一下约束条件, 直接套用Prim算法模板求解

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=2005;
const int INF=0x3f3f3f3f;
int C, n;
bool vis[N];
LL dist[N];
int x[N], y[N];

inline LL dis(int a, int b){return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])>=C?(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]):INF;}

int prim(){
    dist[1]=0;
    LL ans=0;
    for(int i=0; i<n; ++i){
        int node=-1;
        for(int j=1; j<=n; ++j)
            if(!vis[j] && (node==-1 || dist[j]<dist[node])) node=j;
        if(node==-1) break;
        vis[node]=true;
        ans+=dist[node];
        for(int j=1; j<=n; ++j){
            dist[j]=min(dist[j], dis(j, node));
        }
    }
    return ans>=INF?-1:ans;
}

int main(){
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0x00, sizeof vis);
    cin>>n>>C;
    for(int i=1; i<=n; ++i){
        int posx, posy;
        cin>>posx>>posy;
        x[i]=posx;
        y[i]=posy;
    }
    
    cout<<prim()<<endl;
    return 0;
}

生成树

通过bfs算法得到的生成树称为广度优先生成树, 通过dfs算法得到的生成树称为深度优先生成树.

参考文献

信息学奥赛一本通
数据结构教程 施伯乐 复旦大学出版社
ACM国际大学生程序设计竞赛俞勇清华大学出版社
ACW平台