💓最小生成樹演算法大綱

🌟最小生成樹的基本概念

🌻自由樹和生成樹

自由樹（樹）：
1、自由樹就是一個無回路的連通圖（沒有確定根）
2、n個頂點就一定有n-1條邊

生成樹：
1、包含全部頂點
2、n-1條邊全部在圖中

圖的生成樹不惟一，從不同的頂點出發進行遍歷，可以得到不同的生成樹，

🌻最小生成樹

💓普利姆演算法(prim)——模板題

🌟通俗演示

🌟例題描述

🎇🎇🎇傳送門🎇🎇🎇

🌟參考代碼(C++版本)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 510 , INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    //初始化距離陣列
    memset(dist,0x3f,sizeof dist);
    //res中存放最小生成樹的樹邊權重之和
    int res = 0;        
     
    for(int i = 0; i < n;i++)
    {
        int t = -1;
        for(int j = 1; j <= n;j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;
            
            //如果不是第一個點以及距離最小的點距離是正無窮，說明當前距離最近的點，到集合的距離都是正無窮，即當前圖不連通
            if(i && dist[t] == INF) return INF;
            if(i) res += dist[t];
            
            //用t去更新其他點
            for(int j = 1; j <= n;j++)
                dist[j] = min(dist[j],g[t][j]);//注意這里是g[t][j],Dijkstra中是dist[t]+g[t][j]
                
                st[t] = true;
        
    }
    
    return res;
}


int main()
{
    //輸入
    scanf("%d%d",&n,&m);
    //初始化鄰接矩陣
    memset(g,0x3f,sizeof g);
    //建圖
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        //因為是無向圖，所以得建a 到 b 和 b 到 a的
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    
    int t = prim();
    
    if(t == INF ) puts("impossible");
    else printf("%d\n",t);
    
    return 0;
}

🌟演算法模板

Prim演算法實作的流程圖如下：

Prim演算法實作的代碼描述：

	int n;		 		// n表示點數
	int g[N][N];		// 鄰接矩陣，存盤所有邊
	int dist[N];		// 存盤其他點到當前最小生成樹的距離
	bool st[N];			// 存盤每個點是否已經在生成樹中


	// 如果圖不連通，則回傳INF(值是0x3f3f3f3f), 否則回傳最小生成樹的樹邊權重之和
	int prim()
	{
		memset(dist, 0x3f, sizeof dist);
		
		int res = 0;
		for (int i = 0; i < n; i ++ )
		{
			int t = -1;
			for (int j = 1; j <= n; j ++ )
				if (!st[j] && (t == -1 || dist[t] > dist[j]))
					t = j;
			
			if (i && dist[t] == INF) return INF;
			
			if (i) res += dist[t];
			st[t] = true;
			
			for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
		}
		
		return res;
	}

🌟疑難雜癥剖析

一、建圖

    g[a][b] = g[b][a] = min(g[a][b],c);

二、計算最小權值之和

        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];

三、更新

		  for(int j = 1; j <= n;j++)
		     dist[j] = min(dist[j],g[t][j]);

相似，又不完全相似
Dijkstra演算法中，dist陣列維護的是1號點到當前點的距離
Prim演算法中，dist陣列維護的是當前點到已經存在的最小生成樹集合的距離
因此
Dijkstra演算法的更新是將t作為中介，將從1號點到j的距離dist[j] 和 1號點到t,再從t到j的距離dist[t]+g[t][j]作比較，找到最小的權值
Prim演算法的更新則是，t是作為已經確實的最小生成樹集合的代表

💓克魯斯卡爾演算法(Kruskal)——模板題

🌟通俗演示

Kruskal演算法在理解上是比Prim更舒服的

🌟例題描述

🎇🎇🎇傳送門🎇🎇🎇

🌟參考代碼(C++版本)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

int n,m;
int p[N];//并查集

int cnt,res;//cnt存當前加入多少條邊 ; res存放的是最小生成樹中所有樹邊的權重之和

//kruskal演算法可以不用鄰接表存，只要把點和點到點的邊存下來就好
//就不用使用復雜的資料結構，直接結構體搞了，只是要注意多載小于符號，讓sort的時候可以根據權重來比較

struct Edge
{
    int a,b,w;
    
    bool operator < (const Edge &W)const
    {
        return w < W.w;
    }
}edges[N];

//并查集的find函式
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal()
{
    
    //對存放的邊按照權重排序
    sort(edges,edges+m);
    //初始化并查集
    for(int i = 1; i <= n;i++) p[i] = i;

    //從小到大列舉所以邊
    for(int i = 0; i < m; i++) 
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        
        //找到a的祖宗結點
        a = find(a),b = find(b);
        //如果a 和 b 不在一個連通塊中
        if(a !=  b)
        {
            //將a連通到b上
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
}

int main()
{
    
    //輸入
    scanf("%d%d",&n,&m);
    
    //建圖
    for(int i = 0; i < m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i] = {a,b,w};
    }

    kruskal();
    
    //輸出 ：輸出一個整數，表示最小生成樹的樹邊權重之和
    //n個點，因為成最小生成樹只能有n-1邊
    if(cnt < n-1) puts("impossible");
    else printf("%d\n",res);
    return 0;
}

🌟演算法模板

Kruskal演算法的執行流程圖如下;

Kruskal演算法代碼實作：

int n, m;		// n是點數，m是邊數
	int p[N];		// 并查集的父節點陣列

	struct Edge
	{
	    int a,b,w;
	}edges[N];
	
	//自定義比較的方式，待會放置到sort函式中進行比較
	bool cmp(Edge a,Edge b)
	{
	    return a.w < b.w;
	}

	int find(int x)		// 并查集核心操作
	{
		if (p[x] != x) p[x] = find(p[x]);
		return p[x];
	}

	int kruskal()
	{
		sort(edges, edges + m);
		
		for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集
		
		int res = 0, cnt = 0;
		for (int i = 0; i < m; i ++ )
		{
			int a = edges[i].a, b = edges[i].b, w = edges[i].w;
			
			a = find(a), b = find(b);
			if (a != b)		// 如果兩個連通塊不連通，則將這兩個連通塊合并
			{
				p[a] = b;
				res += w;
				cnt ++ ;
			}
		}
		
		if (cnt < n - 1) return INF;
		return res;
	}

🌻疑難雜癥剖析

一、存盤邊

二、并查集的使用
2.1、初始化并查集——讓每個結點做自己的父結點
2.2、并查集的find函式的撰寫

嗯哼？對并查集不了解呀，嗦嘎

演算法基礎系列第二章——出發，淺酌并查集

看到這里的小伙伴看到這里可能會覺得，呀，就這，就這呀？！學會了學會了

💓例題一

🎇🎇🎇傳送門🎇🎇🎇
那咱們先來一道簡單的活動活動筋骨

🌟解題報告

🌻解題思路

🌻參考代碼（C++版本）

🎇🎇🎇點擊這里查看參考代碼喔~🎇🎇🎇

💓例題二

🎇🎇🎇傳送門🎇🎇🎇

🌟解題報告

🌻解題思路

題目要的是一棵方差最小的生成樹
一、數學知識的回憶——方差

二、解決需求——計算方差
這道題要咱們求的方差最小，那么就是要求每條邊的(權重 - 平均值)²的和最小，

因為隨著每次輸入是動態的，所以直接求平均值是比較困難的，這個時候，我們就可以拿出我們可愛的列舉，

我們可以列舉全部邊權和的可能，對于每一個可能，都去執行Kruskal演算法，執行的時候，把(權重 - 平均值)²作為真正要用的權重w，
同時，當我們先前列舉的邊權和等于執行完Kruskal演算法之后的生成樹權值的和，此時就可以更新答案了，

🌻參考代碼(C++版本)

🎇🎇🎇點擊這里查看參考代碼喔~🎇🎇🎇

🌻疑難雜癥剖析

一、執行思路

kruskal演算法執行流程

二、圈定列舉的區間

		//minv就是可能出現的權值和的最小值，maxv則是可能出現的權值之和的最大值
        for(int i = 0; i < n - 1; i++)
            minv += tmp[i];
        for(int i = m - 1; i > m - n; i--)
            maxv += tmp[i];
        for(int i = minv; i <= maxv; i++)
            Kruskal(i);

因為最小生成樹有n-1條邊，

三、謹記需求

    for(int i = 0; i < m; i++)
        e[i].w = (e[i].val - ave) * (e[i].val - ave);
        
	//重新排序
    sort(e, e + m, cmp);

💓例題三

例題描述：

🎇🎇🎇傳送門🎇🎇🎇

🌟解題報告

🌻解題思路

一、第一感受

二、看資料范圍定演算法

最小生成樹演算法大綱

對于這道題而言，從資料范圍可以得知是稠密圖，那么我們就可以回憶一下prim演算法的實作流程然后去逐步落實，

🌻參考代碼(C++版本)

🎇🎇🎇點擊這里查看參考代碼喔~🎇🎇🎇

🌻疑難雜癥剖析

    //輸入
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j<=n;j++) cin >>g[i][j];

💓總結

謝謝友友們耐心觀看啦~，若有偏頗，歡迎及時私信指出喔💖💖💖

基礎演算法持續更新中ing~