最小生成樹專題

最小生成樹

目錄

• 最小生成樹
• • 定義
  • Prim
  • • 大緻思想
    • 代碼模闆
  • Kruskal
  • • 大緻思路
    • 代碼模闆

定義

連通圖：在一個無向圖中，任何兩頂點都可以一若幹條邊連通

生成樹：在一個連通圖中（定點數n），取n-1條邊，這n-1條邊可以把n個點串起來。

最小生成樹：假設每條邊都有一個權值，則最小權值的生成樹是最下生成樹。

Prim

大緻思想

代碼與Dijsktra極其相似。

先找到從目前所在點到相鄰點權值最小的點，将其劃進生成樹，然後更新将這個點的相鄰點走過去所需的權值進行更新進行更新(這一步了解為更新其鄰接點到生成樹的距離)。

代碼模闆

#include <iostream>
#include <cstring>
using namespace std ;
const int N = 100005 ;

int w[505][505];
bool vis[N] ;
int CNTW;
int d[N];




bool prim(int n){
    d[1] = 0 ;
    for(int i = 1 ; i <= n ; i ++){
        int k = 0 ;
        for(int j = 1 ; j <= n ; j ++){
            if(!vis[j] && d[j] < d[k]){
                k = j ;
            }
        }
        if(!k) return false ;
        vis[k] = true ;
        CNTW += d[k] ;
        for(int j = 1 ; j <= n ; j ++){
            if(!vis[j] && d[j] > w[k][j]){
                d[j] = w[k][j] ;
            }
        }
    }
    return true ;
}






int main(){
    memset(d , 0x3f , sizeof d);
    memset(w , 0x3f , sizeof w);
    int n ,m ;
    
    cin >> n >> m ;
    
    
    for(int i = 1 ; i <= m ; i ++ ){
        int a , b , c ;
        cin >> a >> b >> c ;
        w[a][b] = w[b][a] = min(c , w[a][b]) ;
    }
    for(int i = 1 ; i <= n ; i ++){
        w[i][i] = 0 ;
    }
    
    if(prim(n)) cout << CNTW << endl ;
    else puts("impossible");
    
    return 0;
}
           

Kruskal

大緻思路

将所有邊進行一個排序，然後講這些邊從小到大進行處理：如果邊的兩端不在同一個生成樹中，就将其連接配接起來（利用并查集）。

到最後如果連接配接起來的邊數沒有達到n-1，說明不存在最小生成樹。

代碼模闆

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 100005 ;

typedef struct {
    int a , b , c ;
}Edge;

Edge edge[N << 1] ;

bool cmp(Edge a, Edge b ){
    return a.c < b.c ;
}

int p[N] ;

int find(int x){
    if(p[x] != x){
        p[x] = find(p[x]);
    }
    return p[x] ;
}

int main(){
    int n , m ;
    cin >> n >> m ;
    for(int i = 1 ; i <= m ; i ++){
        int a ,b ,c ;
        cin >> a >> b >> c ;
        edge[i] = {a , b , c};
    }
    for(int i = 1 ; i <= n ; i ++ ){
        p[i] = i ;
    }
    sort(edge+1 , edge+1 + m , cmp) ;
    
    int cntw = 0 , cnte = 0 ;
    for(int i = 1 ; i <= m ; i ++){
        int a = edge[i].a , b = edge[i].b , c = edge[i].c ;
        a = find(a) , b = find(b) ;
        if(a != b){
            p[a] = b;
            cntw += c ;
            cnte ++ ;
        }
    }
    
    if(cnte < n -1 ) puts("impossible");
    else cout << cntw << endl ;
    return 0 ;
}