程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++,Kruskal克魯斯卡爾算法求最小生成樹

C++,Kruskal克魯斯卡爾算法求最小生成樹

編輯:關於C++

C++,Kruskal克魯斯卡爾算法求最小生成樹。本站提示廣大學習愛好者:(C++,Kruskal克魯斯卡爾算法求最小生成樹)文章只能為提供參考,不一定能成為您想要的結果。以下是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;
    
}
View Code

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved