前言

本篇博客介紹兩種求最小生成樹的方法：即Prime算法和Kruskal算法。Prime算法用于稠密圖，也可以與Dijkstra類似用堆優化（詳見《圖論 - 最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）》），用于稀疏圖，但是稀疏圖的時候求最小生成樹，Kruskal 算法更加實用，所以本篇博客將不介紹堆優化的Prime算法。即：稠密圖用樸素Prime算法，稀疏圖用Kruskal 算法即可。

Part 1：Prim算法求最小生成樹

1.題目描述

給定一個 n 個點 m 條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。

求最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

給定一張邊帶權的無向圖 G=(V,E)，其中 V 表示圖中點的集合，E 表示圖中邊的集合，n=|V|，m=|E|。

由 V 中的全部 n 個頂點和 E 中 n?1 條邊構成的無向連通子圖被稱為 G 的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖 G 的最小生成樹。

輸入格式

第一行包含兩個整數 n 和 m。

接下來 m 行，每行包含三個整數 u,v,w，表示點 u 和點 v 之間存在一條權值為 w 的邊。

輸出格式

共一行，若存在最小生成樹，則輸出一個整數，表示最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

數據范圍

1≤n≤500,
1≤m≤10⁵,
圖中涉及邊的邊權的絕對值均不超過 10000。

輸入樣例

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

輸出樣例

6

2.算法

• prim 算法采用的是一種貪心的策略
• prim 算法做的事情是：給定一個無向圖，在圖中選擇若干條邊把圖的所有節點連起來。要求邊長之和最小。在圖論中，叫做求最小生成樹
• 每次將離連通部分的最近的點和點對應的邊加入的連通部分，連通部分逐漸擴大，最后將整個圖連通起來，并且邊長之和最小
• 與Dijkstra算法求最短路唯一的區別在于所求距離并非該點到源點的距離（詳見《圖論 - 最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）》），而是該點到已選點集合的最短距離

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 510;
int g[N][N];//存儲圖
int dt[N];//存儲各個節點到生成樹的距離
int st[N];//節點是否被加入到生成樹中
int pre[N];//節點的前去節點
int n, m;//n 個節點，m 條邊void prim()
{memset(dt,0x3f, sizeof(dt));//初始化距離數組為一個很大的數（10億左右）int res= 0;dt[1] = 0;//從 1 號節點開始生成 for(int i = 0; i < n; i++)//每次循環選出一個點加入到生成樹{int t = -1;for(int j = 1; j <= n; j++)//每個節點一次判斷{if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果沒有在樹中，且到樹的距離最短，則選擇該點t = j;}//如果孤立點，直返輸出不能，然后退出if(dt[t] == 0x3f3f3f3f) {cout << "impossible";return;}st[t] = 1;// 選擇該點res += dt[t];for(int i = 1; i <= n; i++)//更新生成樹外的點到生成樹的距離{if(dt[i] > g[t][i] && !st[i])//從 t 到節點 i 的距離小于原來距離，則更新。{dt[i] = g[t][i];//更新距離pre[i] = t;//從 t 到 i 的距離更短，i 的前驅變為 t.}}}cout << res;}void getPath()//輸出各個邊
{for(int i = n; i > 1; i--)//n 個節點，所以有 n-1 條邊。{cout << i <<" " << pre[i] << " "<< endl;// i 是節點編號，pre[i] 是 i 節點的前驅節點。他們構成一條邊。}
}int main()
{memset(g, 0x3f, sizeof(g));//各個點之間的距離初始化成很大的數cin >> n >> m;//輸入節點數和邊數while(m --){int a, b, w;cin >> a >> b >> w;//輸出邊的兩個頂點和權重g[a][b] = g[b][a] = min(g[a][b],w);//存儲權重}prim();//求最下生成樹//getPath();//輸出路徑return 0;
}

Part 2：Kruskal算法求最小生成樹

1.題目描述

給定一個 n 個點 m 條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。

求最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

給定一張邊帶權的無向圖 G=(V,E)，其中 V 表示圖中點的集合，E 表示圖中邊的集合，n=|V|，m=|E|。

由 V 中的全部 n 個頂點和 E 中 n?1 條邊構成的無向連通子圖被稱為 G 的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖 G 的最小生成樹。

輸入格式

第一行包含兩個整數 n 和 m。

接下來 m 行，每行包含三個整數 u,v,w，表示點 u 和點 v 之間存在一條權值為 w 的邊。

輸出格式

共一行，若存在最小生成樹，則輸出一個整數，表示最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

數據范圍

1≤n≤10⁵,
1≤m≤2?10⁵,
圖中涉及邊的邊權的絕對值均不超過 1000。

輸入樣例

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

輸出樣例

6

2.算法

• prim 算法采用的是一種貪心的策略
• 將所有邊按照權值的大小進行升序排序，然后從小到大一一判斷
• 如果這個邊與之前選擇的所有邊不會組成回路（用并查集判斷），就選擇這條邊分；反之，舍去
• 直到具有 n 個頂點的連通網篩選出來 n-1 條邊為止
• 篩選出來的邊和所有的頂點構成此連通網的最小生成樹

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int p[N];//保存并查集struct E
{int a;int b;int w;//通過邊長進行排序bool operator < (const E& rhs){return this->w < rhs.w;}}edg[N * 2];int res = 0;
int n, m;
int cnt = 0;//并查集找祖宗
int find(int a)
{if(p[a] != a) p[a] = find(p[a]);return p[a];
}void klskr()
{//依次嘗試加入每條邊for(int i = 1; i <= m; i++){int pa = find(edg[i].a);// a 點所在的集合int pb = find(edg[i].b);// b 點所在的集合//如果 a b 不在一個集合中if(pa != pb){res += edg[i].w;//a b 之間這條邊要p[pa] = pb;// 合并a bcnt ++; // 保留的邊數量+1}}
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++) p[i] = i;//初始化并查集//讀入每條邊for(int i = 1; i <= m; i++){int a, b , c;cin >> a >> b >>c;edg[i] = {a, b, c};}sort(edg + 1, edg + m + 1);//按邊長排序klskr();//如果保留的邊小于點數-1，則不能連通if(cnt < n - 1) {cout<< "impossible";return 0;}cout << res;return 0;
}