最小生成树总结

最小生成树的性质:
(1)最小生成树并不唯一,准确的来说是最小生成树的树形并不唯一
(2)最小生成树的权值之和唯一,并且是最小的
(3)最小生成树的边数 = 顶点数-1
求最小生成树有两种经典算法:普里姆算法(prim)和克鲁斯卡尔(kruskal)算法
算法比较：时间复杂度比较 https://blog.csdn.net/qq1169091731/article/details/51661605
Prim在稠密图中比Kruskal优,在稀疏图中比Kruskal劣
Prim堆优化效果最好，但是空间花费大，代码复杂

krusal这个写法更简单写以及理解一些。

模板：

prim(堆优化/优先队列/向前星)：

题目参考：

POJ - 1251 Jungle Roads （prim模板）

POJ - 1287 Networking (prim)

POJ - 2031 Building a Space Station （prim）

ZOJ - 1586 QS Network (kruskal,prim)

FZU - 2254 英语考试（最小生成树）

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
const int maxm = 1e5;
const int inf = 0x3f3f3f3f;
const int maxn = 30;
int top;
int n,m;
int ans;
int head[maxn];
int vis[maxn];
int dist[maxn];
//堆重载 
struct cmp{
    bool operator() (pii a, pii b){
        return a.first>b.first;
    }
};
struct Edge{
    int u,v,w;
    int next;
}edge[maxm];

void init(){
    memset(head,-1,sizeof(head));
    memset(edge,0,sizeof(edge));
    memset(dist,-1,sizeof(dist));
    memset(vis,0,sizeof(vis));
    top = 0;
    ans = 0;
}
void add(int v,int u,int w){
    edge[top].u = u;
    edge[top].v = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top++;
}
void prim(int s){
    int i;
    priority_queue<pii,vector<pii> ,cmp>Q;
    dist[s] = 0;
    vis[s] = 1;
    for(i = head[s]; ~i; i = edge[i].next){
        //先把到起点边的距离初始化为其本身 
        dist[edge[i].v] = edge[i].w;
        Q.push(make_pair(dist[edge[i].v],edge[i].v));
    }
    while(!Q.empty()){
        pii t = Q.top();
        Q.pop();
        if(vis[t.second]) continue;
        ans += t.first;
        vis[t.second] = 1;
        for(i = head[t.second]; ~i ;i = edge[i].next){
            int j = edge[i].v;
            //没被访问没有连接或者权值太小 
            if(!vis[j]&&(dist[j]>edge[i].w||dist[j]==-1)){
                dist[j] = edge[i].w;
                Q.push(make_pair(dist[j],j));
            }
        }
    }
}

krusal （并查集）：

题目参考：ZOJ - 1586 QS Network (kruskal,prim)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e4;//点数
const int maxm=1e6+10;//边数
int pre[maxn];
int cost[maxn];
struct Edge{
    int u,v,w;
}edge[maxm];
int top; 
int cnt;
int ans;

void addedge(int u,int v,int w){
    edge[top].u=u;
    edge[top].v=v;
    edge[top++].w= w ;
} 
bool cmp(Edge a,Edge b) {
    return a.w<b.w; 
}
int find(int x)
{
    if(x!=pre[x]) return pre[x] = find(pre[x]);
    else return pre[x];
}
bool unite(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy) {
        pre[fx] = fy;
        cnt++;    
        return true;
    }
    else return false;
}
int Kruskal(int n){
    sort(edge,edge+top,cmp);//一次性把所有的边都排了 
    int u,v,w;
    for(int i=0;i<top;i++){
        u=edge[i].u;   
        v=edge[i].v;   
        w=edge[i].w; 
        if(unite(u,v)){
            ans += w;    
        }
        if(cnt==n-1) break;
    }
    if(cnt<n-1) return -1;
    return ans;
}
void init(int n){
    memset(edge,0,sizeof(edge));
    for(int i=0;i<=n;i++)
        pre[i] = i;
    ans = top = cnt = 0;
}