最小生成樹Kruscal算法（C++）-創(chuàng)新互聯

求點贊，求關注，小UP想變大UP的夢想就靠你實現了！

最近新入了一個畫圖軟件，講講圖論再合適不過了

創(chuàng)新互聯建站"三網合一"的企業(yè)建站思路。企業(yè)可建設擁有電腦版、微信版、手機版的企業(yè)網站。實現跨屏營銷，產品發(fā)布一步更新，電腦網絡+移動網絡一網打盡，滿足企業(yè)的營銷需求！創(chuàng)新互聯建站具備承接各種類型的網站制作、成都網站設計項目的能力。經過十年的努力的開拓，為不同行業(yè)的企事業(yè)單位提供了優(yōu)質的服務，并獲得了客戶的一致好評。引入

我們來看這樣一個東西

找到一棵樹，邊長之和最小，也就是最小生成樹

一個一個選DFS，太慢了?

那怎么辦呢？

Kruscal

我們注意到，邊長之和最小

那我們優(yōu)先選邊長之和最小就可以了呀

但要選的是一棵樹，如果按這個想法，可能會有回路產生，那就不好了

我們之前講了并查集

想一下，可以用并查集嗎

我們看兩個點的最老的祖先節(jié)點，如果兩個是同一個點，就不能選了

我們的想法就好了

設每一條邊是x-y，長度為k，我們按照k排序，如果兩個點x,y的最老的祖先節(jié)點一樣，那這條邊就不添加

我們來模擬一下樣例

選中的邊紅色，不能連的黃色，剩下最小的綠色，沒連的藍色

當你連了點數N-1條邊，就是一顆最小生成樹

圖例1

最終的最小生成樹（這個圖不太好，沒有黃色的邊出現）

再來一個?

圖例2?

并查集告訴我們AC不能連

至此，最小生成樹產生了

原理講完了，我們看題

例1

登錄 - 沐楓OJhttps://www.mfstem.org/p/688可以說模板題，沒啥好講的，代碼里有注釋講解，自己看吧

#includeusing namespace std;
#define int long long
int n,tp,f[10005],sum,ans;
struct road{//定義x,y,t
	int x;
	int y;
	int t;
}r[100005];
bool cmp(road a,road b){//排序
	return a.t< b.t;
} 
int fi(int x){
	return f[x] == x ? x : f[x] = fi(f[x]);//找最老的祖先
}
signed main(){
	cin >>n;
    for(int i = 1;i<= n;++i){
        f[i] = i;//注意初始化
        for(int j = 1,a;j<= n;++j){//讀入
            cin >>a;
            if(i< j){
                ++tp;
                r[tp].x = i,r[tp].y = j,r[tp].t = a;//添加邊
            }
        }
    }
	sort(r + 1,r + tp + 1,cmp);//排序
	for(int i = 1;i<= tp;++i){
		int q = fi(r[i].x),p = fi(r[i].y);//找最老的祖先
		if(q != p){
			++sum;
			f[q] = p;//認“爸爸”
			ans += r[i].t;//加邊權
		}
		if(sum == n - 1){//滿足要求，退出
			cout<< ans<< endl;
			return 0;
		}
	}
	return 0;
}
練習：

登錄 - 沐楓OJhttps://www.mfstem.org/p/692我的AC代碼：

#includeusing namespace std;
#define int long long
int n,tp,f[2005],sum,ans,m;
struct road{
	int x;
	int y;
	int t;
}r[10005];
bool cmp(road a,road b){
	return a.t< b.t;
} 
int fi(int x){
	return ((f[x] == x) ? x : f[x] = fi(f[x]));
}
signed main(){
	cin >>n >>m;
    for(int i = 1;i<= n;++i)f[i] = i;
    for(int i = 1,p,xx,yx,tx;i<= m;++i){
        cin >>p >>xx >>yx >>tx;
        if(p == 1){
            ans += tx;
			int xxx = fi(xx),yyy = fi(yx);
            if(xxx != yyy)f[xxx] = yyy,++sum;
        }
        else{
            ++tp;
            r[tp].x = xx,r[tp].y = yx,r[tp].t = tx;
        }
    }
	if(sum >= n - 1){
		cout<< ans<< endl;
		return 0;
	}
	// cout<< tp<< endl;
	sort(r + 1,r + tp + 1,cmp);
	for(int i = 1;i<= tp;++i){
        // cout<< r[i].x<< " "<< r[i].y<< endl;
		int q = fi(r[i].x),p = fi(r[i].y);
		if(q != p){
			f[q] = p;
			ans += r[i].t;
			++sum;
			// for(int j = 1;j<= n;++j)cout<< f[j]<< " ";
			// cout<< endl;
		}
		if(sum == n - 1){
			cout<< ans<< endl;
			return 0;
		}
	}
	return 0;
}

代碼我就不解釋了，要做完才能看代碼喲

下期講講基礎A+B，敬請期待

拜了個拜！

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站題目：最小生成樹Kruscal算法（C++）-創(chuàng)新互聯
轉載來于：http://bm7419.com/article14/ihgde.html

成都網站建設公司_創(chuàng)新互聯，為您提供靜態(tài)網站、Google、關鍵詞優(yōu)化、云服務器、營銷型網站建設、企業(yè)網站制作

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯

成都做網站