prim算法

複雜度： o ( n 2 ) o(n^2) o(n2)，n為節點數

prim算法是一種基于貪心的算法，主要流程是：首先，将任意一點（習慣是1）加入樹中，之後，選擇和1相連的所有邊，選擇最短的路徑，把該路徑和點加入樹中，接着繼續掃描新加入的點，直到邊數達到n-1，形成樹為止。

洛谷P3366 模闆：最小生成樹

先貼下闆子：

ll prim(){//防爆
    int res=0;
    rep(i,2,n){
        dis[i]=INT_MAX;//把所有距離都設定為inf，友善比較
    }
    for(int i=head[1];~i;i=e[i].next){
        dis[e[i].to]=min(dis[e[i].to],e[i].w);//把1加入後，尋找和1相連的所有邊中最短的。
    }
    int now=1;
    int counter=0;
    while(counter<n-1){//需要找到n-1條邊
        int mi=INT_MAX;
        vis[now]=1;
        rep(i,1,n){
            if(!vis[i]&&mi>dis[i]){
                mi=dis[i];
                now=i;//尋找目标邊和節點
            }
        }
        res+=mi;//更新答案
        counter++;
        for(int i=head[now];~i;i=e[i].next){
            int v=e[i].to;
            if(vis[v]) continue;
            dis[v]=min(dis[v],e[i].w);
        }
    }
    return res;
}

以上是用暴力的方式完成的prim算法，後面還可以利用堆進行優化。

AC代碼

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
 
template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
	ll ans=1;
	while(n){
		if(n&1) ans=(ans*a)%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans%mod;
}
const int maxn=2e5+10;
struct Edge{
    int next,w,to;
}e[maxn<<1];
int cnt,head[maxn];
void add(int x,int y,int w){
    e[cnt].to=y;
    e[cnt].next=head[x];
    e[cnt].w=w;
    head[x]=cnt++;
}
int n,m;
int dis[maxn];
int vis[maxn];
ll prim(){
    int res=0;
    rep(i,2,n){
        dis[i]=INT_MAX;
    }
    for(int i=head[1];~i;i=e[i].next){
        dis[e[i].to]=min(dis[e[i].to],e[i].w);
    }
    int now=1;
    int counter=0;
    while(counter<n-1){
        int mi=INT_MAX;
        vis[now]=1;
        rep(i,1,n){
            if(!vis[i]&&mi>dis[i]){
                mi=dis[i];
                now=i;
            }
        }
        res+=mi;
        counter++;
        for(int i=head[now];~i;i=e[i].next){
            int v=e[i].to;
            if(vis[v]) continue;
            dis[v]=min(dis[v],e[i].w);
        }
    }
    return res;
}
int vis2[maxn];
void dfs(int u){
    vis2[u]=1;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(vis2[v]) continue;
        dfs(v);
    }
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	//===========================================================
	read(n),read(m);
    memset(head,-1,sizeof(head));
    rep(i,1,m){
        int x,y,w;
        read(x),read(y),read(w);
        add(x,y,w),add(y,x,w);
    }
    int ans=prim();
    dfs(1);
    rep(i,1,n){
        if(vis2[i]==0){
            cout<<i<<endl;
            cout<<"orz"<<endl;
            return 0;
        }
    }
    write(ans);
	//===========================================================
	return 0;
}

堆優化

複雜度： ( n l o g n ) (nlogn) (nlogn)，n為節點數

之後可以利用堆優化，其實就是利用堆選擇目前的最優選項。

priority_queue<Edge> que;
int vis[maxn];
int num;
ll prim(){
    ll res=0;
    vis[1]=1;
    num++;
    for(register int i=head[1];~i;i=e[i].next){
        int v=e[i].to;
        if(vis[v]) continue;
        que.push(e[i]);
    }
    while(!que.empty()){
        Edge a=que.top();
        que.pop();
        int u=a.to;
        if(vis[u]) continue;
        vis[u]=1;
        num++;
        res+=a.w;
        for(register int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(vis[v]) continue;
            que.push(e[i]);
        }

    }
    return res;
}

題目是：https://ac.nowcoder.com/acm/problem/20568

這道題主要的坑點在于有的情況下要建立雙向邊，其他的就是裸的最小生成樹問題了。

kruskal算法

複雜度： e l o g e eloge eloge，e為邊的數目

kruskal算法相對prim算法更好寫，更暴力。鍊式前向星？不需要，什麼圖都不用存，直接存邊的起始點、終點、權值就行了。之後按邊權sort一下，然後逐一往樹中加入這些邊。同時，利用并查集判斷加入邊後是否會形成環（邊的兩個頂點是否在加入該邊前已經連結在一起了），直到加入n-1條邊為止。

模闆：

const int maxn=2e5+10;
int s[maxn];
int n,m;
struct Edge{
    int u,v,w;
}e[maxn];
bool cmp(const Edge&a,const Edge&b){
    return a.w<b.w;
}
void init(){
    rep(i,1,n) s[i]=i;
}
inline int find(int x){
    if(x==s[x]) return x;
    int r=x;
    while(s[r]!=r) r=s[r];
    while(x!=r){
        int t=s[x];
        s[x]=r;
        x=t;
    }
    return r;
}


inline ll kruskal(){
    ll res=0;
    sort(e,e+m,cmp);
    int cnt=0;
    rep(i,0,m-1){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        s[u]=v;
        res+=e[i].w;
        cnt++;
        if(cnt==n-1) return res; 
    }
}

洛谷模闆題：

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
 
template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
	ll ans=1;
	while(n){
		if(n&1) ans=(ans*a)%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans%mod;
}
const int maxn=2e5+10;
int s[maxn];
int n,m;
struct Edge{
    int u,v,w;
}e[maxn];
bool cmp(const Edge&a,const Edge&b){
    return a.w<b.w;
}
void init(){
    rep(i,1,n) s[i]=i;
}
inline int find(int x){
    if(x==s[x]) return x;
    int r=x;
    while(s[r]!=r) r=s[r];
    while(x!=r){
        int t=s[x];
        s[x]=r;
        x=t;
    }
    return r;
}


inline ll kruskal(){
    ll res=0;
    sort(e,e+m,cmp);
    int cnt=0;
    rep(i,0,m-1){
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        s[u]=v;
        res+=e[i].w;
        cnt++;
        if(cnt==n-1) return res; 
    }
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	//===========================================================
    read(n),read(m);
	init();
    rep(i,1,m){
        read(e[i].u),read(e[i].v),read(e[i].w);
    }
    write(kruskal());
	//===========================================================
	return 0;
}

比較

prim算法的複雜度和節點數有關，與邊數無關，是以，适合稠密圖。

kruskal算法複雜度與邊數有關，與節點數無關，是以，适合稀疏圖。

【圖論】最小生成樹算法：prim算法和kruskal算法prim算法kruskal算法比較

目錄

prim算法

AC代碼

堆優化

kruskal算法

比較

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希