【模闆】Kruskal算法求最小生成樹

文章目錄

• 1.Kruskal算法介紹
• 2.模闆實作
• 3.例題

1.Kruskal算法介紹

克魯斯卡爾算法可以稱為“加邊法”，初始最小生成樹邊數為0，每疊代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合裡。

1. 把圖中的所有邊按代價從小到大排序；
2. 把圖中的n個頂點看成獨立的n棵樹組成的森林；
3. 按權值從小到大選擇邊，所選的邊連接配接的兩個頂點ui,viui,vi,應屬于兩顆不同的樹，則成為最小生成樹的一條邊，并将這兩顆樹合并作為一顆樹。
4. 重複(3),直到所有頂點都在一顆樹内或者有n-1條邊為止。

   

總結：從小開始加，確定無回路(樹)

|| 差別普利姆最小生成樹算法：普利姆算法從頂點的角度為出發點。時間複雜度為O(n^2)。**更适合于稠密度更高的連通網**。 而克魯斯卡爾算法從邊的角度求最小生成樹，時間複雜度為O(eloge)，**更适合于稠密度更高的連通網**。

|| 判斷是否會産生回路的方法為： 在初始狀态下給每個頂點賦予不同的标記，對于周遊過程的每條邊，其都有兩個頂點，判斷這兩個頂點的标記是否一緻，如果一緻，說明它們本身就處在一棵樹中，如果繼續連接配接就會産生回路；如果不一緻，說明它們之間還沒有任何關系，可以連接配接。

2.模闆實作

//最小生成樹（Kruskal算法）
#include<iostream>
#include<algorithm>
using namespace std;

struct point{
    int x;
    int y;
    int v;
}; //寫結構體用來構造邊 
point a[10000];//存邊
 
int cmp(const point &a,const point &b){
    if(a.v<b.v) return 1;
    else return 0;
}//快排要用到的比較函數 ，從小到大
 
int fat[101];
int father(int x){
    if(fat[x]!=x) return fat[x]=father(fat[x]);
    else return fat[x];
}//找出一個點屬于哪個集合（找這個點的爹） 

void unionn(int x,int y){
    int fa=father(x);
    int fb=father(y);
    if(fa!=fb) fat[fa]=fb;
}//将被邊連接配接的兩個獨立集合合并 

int main(){
    int i,j,n,m,k=0,ans=0,cnt=0;
    cin>>n;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        cin>>m;
        if(m!=0){
            k++;
            a[k].x=i;
            a[k].y=j;
            a[k].v=m;
        }
    }//輸入，存邊 
    sort(a+1,a+1+k,cmp);//快排所有邊 
    
    for(i=1;i<=n;i++){
        fat[i]=i;
    }//初始化，将每個點看做獨立集合 
    
    for(i=1;i<=k;i++){
        if(father(a[i].x)!=father(a[i].y)){//如果這條邊連接配接的兩個點屬于不同集合 
            ans+=a[i].v;//将這條邊加入最小生成樹 
            unionn(a[i].x,a[i].y);//将兩個點所在的集合合并為一個集合 
            cnt++;//計數已添加的邊 
        }
        if(cnt==n-1) break;//當已經有n-1條邊的時候，結束 
    }
    
    cout<<ans;
    return 0;
    
}
           

/

3.例題

///解法