MST

Minimum Spanning Tree(最小生成樹)

1.Kruskal’s Algorithm

利用貪心法,先對權重排序,從權重較大的開始,檢查新增的這條邊是否有環,沒有的話就利用並查集把這兩個點合併,並把權重加到sum,最後輸出就完成啦~

1. disjoin set初始化

int dis[MAXN],num[MAXN],n,ma=1;

void init(){
    for(int i=0;i<n;i++){
        dis[i]=i;
        num[i]=1;
    }
}

2. 依照權重排序

struct node{
  int x,y,v;
};
vector<node> node;

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

sort(node.begin(),node.end(),cmp);

3. 合併

bool uni(int a,int b){
    if(fa(a)==fa(b)) return false;
    
    num[fa(a)]+=num[fa(b)];
    ma=max(ma,num[fa(a)]);  //檢查最大並查集有沒有包括全部的點,如果沒有代表此圖不是完全連通圖
    dis[fa(b)]=fa(a);
    return true;
}

4. 主程式

int ans=0,cnt=0;
for(node now:a){
    if(uni(now.x,now.y)){  //合併成功,兩點屬於集合不同
        ans+=now.w;
    }
}
if(ma==n) cout << ans << '\n';   
else cout << -1 << '\n';  //不是完全連通圖

2.Prim's Algorithm

d[i]陣列為當前i節點距離最小生成樹的最小距離

1. 初始化
2. 找到距離最小生成數權重最小的邊
3. 把最小生成樹加上該邊
4. 更新d陣列

int prim(int n){
  int edge=1,sum=0;
  //初始化
  for(int i=0;i<n;i++){
    d[i]=1e9;
    used[i]=0;
  }
  d[0]=0;
  
  for(int i=0;i<n;i++){
    //找距離最小生成樹的最小邊
    int index,mi=INT_MAX;
    for(int j=0;j<n;j++){
      if(!used[j] && d[j]<mi){
        mi=d[j];
        index=j;
      }
    }
    
    if(mi==INT_MAX) break;
    used[index]=true;
    sum+=mi;
    edge++;
    //更新鄰接新增的點距離最小生成數的權重
    for(int j=0;j<n;j++){
      if(!used[j] && map[index][j]<d[j]){
        d[j]=map[index][j];
      }
    }
  }
  return edge==n?sum:-1;
}

set優化

priority_queue<pii,vector<pii>,greater<pii>> pq;  //每次選距離MST最短距離的vertex
pq.push({0,0});

int ans=0,cnt=n;
while(!pq.empty()){
    pii now=pq.top();pq.pop();
    if(confirm[now.idx]) continue;

    ans+=now.val;
    confirm[now.idx]=true;  //設為確定值
    cnt--;
    for(auto i:Map[now.idx]){
        if(!confirm[i.idx]){
            pq.push({i.val,i.idx});
        }
    }
}
if(cnt==0) cout << ans << '\n';   
else cout << -1 << '\n';  //沒有所有點連通

注意!!! 與dijkstra差別在prim's要設confirm陣列,而Dijkstra則是設一個到該點最小距離的陣列

因為dijkstra是求單源到各個點的最短路徑,所以判斷式是這樣

if(now.val>dis[now.x][now.y]) continue;

但prim's是求距離最小生成樹的距離,如果用dis陣列紀錄的話,每次新增一個元素都會改變最小生成樹的位置,所以應該用used陣列紀錄是否確定為最小生成樹

if(confirm[now.node]) continue;

題目

d098: P-7-12. 最小生成樹
//Kruskal’s Algorithm比較快,但相對的Code就比較持長

Kruskal’s Algorithm

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

struct node{
    int x,y,w;
};

int dis[MAXN],num[MAXN],n,m,x,y,w,ma=1;
vector<node> a;

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

void init(){
    for(int i=0;i<n;i++){
        dis[i]=i;
        num[i]=1;
    }
}

int fa(int a){
    if(dis[a]==a) return a;
    return dis[a]=fa(dis[a]);
}

bool uni(int a,int b){
    if(fa(a)==fa(b)) return false;
    num[fa(a)]+=num[fa(b)];
    ma=max(ma,num[fa(a)]);
    dis[fa(b)]=fa(a);
    return true;
}

int main(){
    cin >> n >> m;
    init();
    while(m--){
        cin >> x >> y >> w;
        a.push_back({x,y,w});
    }
    sort(a.begin(),a.end(),cmp);

    int ans=0,cnt=0;
    for(node now:a){
        if(uni(now.x,now.y)){
            ans+=now.w;
        }
    }
    if(ma==n) cout << ans << '\n';   
    else cout << -1 << '\n';
}

Prim's Algorithm

##include <bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define pii pair<int,int>
#define val first 
#define idx second

int a[MAXN],dis[MAXN];
vector<pii> Map[MAXN];
bool confirm[MAXN];

int main(){
    
    int n,m,x,y,w;
    cin >> n >> m;
    while(m--){
        cin >> x >> y >> w;
        Map[x].push_back({w,y});
        Map[y].push_back({w,x});
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,0});
    
    int ans=0,cnt=n;
    while(!pq.empty()){
        pii now=pq.top();pq.pop();
        if(confirm[now.idx]) continue;
        
        ans+=now.val;
        confirm[now.idx]=true;
        cnt--;
        for(auto i:Map[now.idx]){
            if(!confirm[i.idx]){
                pq.push({i.val,i.idx});
            }
        }
    }
    if(cnt==0) cout << ans << '\n';   
    else cout << -1 << '\n';
}