C++,Kruskal

第一篇博客。

克魯斯卡爾求最小生成樹思想：首先將n個點看做n個獨立的集合，將所有邊快排（從小到大）。然後，按排好的順序枚舉每一條邊，判斷這條邊連接的兩個點是否屬於一個集合。若是，則將這條邊加入最小生成樹，並將兩個點所在的集合合併為一個集合。若否，則跳過。直到找到n-1條邊為止。

#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;
    
}