今天要介紹兩中最小生成樹的算法，分別是prim算法和kruskal算法。
最小生成樹是所有節點的最小連通子圖，即：以最小的成本（邊的權值）將圖中所有節點鏈接到一起。
圖中有n個節點，那么一定可以用n-1條邊將所有節點連接到一起。
那么如何選擇這n-1條邊就是最小生成樹算法的任務所在。
prim算法：
prim算法是從節點的角度采用貪心的策略每次尋找距離最小生成樹最近的節點并加入到最小生成樹中。prim算法核心就是以下三步：
- 第一步，選距離生成樹最近非生成樹節點
- 第二步，最近節點加入生成樹
- 第三步，更新非生成樹節點到生成樹的距離（即更新ans數組）
ans數組用來記錄每一個節點距離最小生成樹的最近距離?
這樣我們只需要遍歷n-1此就能將所有的n-1條最優邊給找出來！每次循環都是以上三個步驟，每次的步驟三都能選出一條最優的邊，因為步驟一是從ans數組中找的，是目前所有的可達點中代價最小的選擇，然后以當前的選擇為起點開始遍歷剩余的新的可達點以及更新其他可達點的距離最小生成樹最近的距離，貪心體現在所有的與最小生成樹相連的節點中找出一個代價最小的，不斷的以當前最優解去遍歷它的可達的節點。?
prim模板（鄰接矩陣 + 遍歷）
最小生成樹prim算法的模板：ICPCer可拿 ！
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int inf = 0x3f3f3f3f; // 代替MAX，標準無窮大表示void solve() {int n, m;cin >> n >> m;vector<vector<int>> e(n + 1, vector<int>(n + 1, inf)); // 鄰接矩陣，初始為infvector<bool> v(n + 1, false); // 是否在MST中vector<int> ans(n + 1, inf); // 存儲各點到MST的最小距離// 建圖，處理重邊for (int i = 1; i <= m; i++) {int u, v, x;cin >> u >> v >> x;e[u][v] = e[v][u] = min(e[u][v], x); // 無向圖，取最小邊}ans[1] = 0; // 從節點1開始構建MST（可任選起點）int res = 0; // 最小生成樹權值和for (int i = 1; i <= n; i++) { // 循環n次，每次加入一個節點int mi = inf, index = -1;// 1. 選取未訪問的、距離MST最近的節點for (int j = 1; j <= n; j++) {if (!v[j] && ans[j] < mi) {mi = ans[j];index = j;}}if (index == -1) { // 圖不連通cout << "No MST" << endl;return;}v[index] = true; // 2. 加入MSTres += mi;// 3. 更新未訪問節點到MST的距離for (int j = 1; j <= n; j++) {if (!v[j] && e[index][j] < ans[j]) {ans[j] = e[index][j];}}}cout << res << endl;
}int main() {IOS;int T = 1;// cin >> T;while (T--) solve();return 0;
}prim模板（鄰接表 + 優先隊列）?
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
const int inf = 0x3f3f3f3f; // 標準無窮大void solve() {int n, m;cin >> n >> m;vector<vector<pii>> e(n + 1); // 鄰接表：e[u] = {v, w}vector<bool> vis(n + 1, false); // 是否在MST中vector<int> dis(n + 1, inf); // 存儲各點到MST的最小距離priority_queue<pii, vector<pii>, greater<pii>> pq; // 小根堆：{w, u}// 建圖（無向圖）for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;e[u].push_back({v, w});e[v].push_back({u, w});}// 從節點1開始（可任選起點）dis[1] = 0;pq.push({0, 1});int res = 0, cnt = 0; // res: MST權值和，cnt: 已加入節點數while (!pq.empty() && cnt < n) {auto [w, u] = pq.top(); pq.pop();if (vis[u]) continue; // 跳過已訪問節點vis[u] = true; // 加入MSTres += w;cnt++;// 更新鄰接節點到MST的距離for (auto [v, w] : e[u]) {if (!vis[v] && w < dis[v]) {dis[v] = w;pq.push({w, v});}}}cout << (cnt == n ? res : -1) << endl; // 輸出-1表示圖不連通
}int main() {IOS;int T = 1;// cin >> T;while (T--) solve();return 0;
}下面來看一道經典的最小生成樹的模版題：（純模板 因為用以上兩個模板均可通過）
尋寶
題目鏈接：尋寶
這就是最小生成樹的prim算法的模版題了，題目要求這幾條路徑中能夠將所有點連接到一起的最短路徑之和，也就是能夠聯通所有節點的最小代價，這時候就可以利用prim這一算法：
首先將所有的節點之間的代價用鄰接矩陣存起來，因為是稠密圖（點少邊多所以用鄰接矩陣），然后以節點1為最小生成樹的根（以哪個都可以，1復合正常的邏輯而已），開始三部曲，第一二步就是選出了1作為起點，第三步就是遍歷了所有與1相連的點，然后更新距離，此時來到了第二次循環還是到了第一步，在這幾個點中找出距離最小生成樹最近的節點并將其加入到最小生成樹中（因為必須按照題目中所給的路徑來，在前面的循環中就已經將目前能走的所有的路徑以及可達點都走過了）所以要在這幾個可達點中選出一條代價最小的路徑，以此類推即可。注意這道題會卡內存，需要在輸入n和m之后動態分配數組大小！
代碼如下：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e4+10;
const int MAX = 10001;
int n,m;
void pre_handle()
{} void solve()
{cin>>n>>m;vector<vector<int>> e(n+1,vector<int>(n+1,MAX));//鄰接矩陣：點少邊多的情況更實用vector<bool> v(n+1,false);//是否在最小生成樹中vector<int> ans(n+1,MAX);//用于存放每個點到最小生成樹的最短距離（最小代價）for(int i=1;i<=m;i++){int u,v,x;cin>>u>>v>>x;e[u][v] = x;e[v][u] = x;}int res=0;for(int i=2;i<=n;i++)//循環n-1次即可{int mi = MAX;int index = 1;// 1、prim三部曲，第一步：選距離生成樹最近節點for(int j=1;j<=n;j++)//找非生成樹中距離最小生成樹中的最小距離{// 選取最小生成樹節點的條件：// （1）不在最小生成樹里// （2）距離最小生成樹最近的節點if(!v[j] && ans[j] < mi){//在所有的與最小生成樹相連的節點中找出一個代價最小的mi = ans[j];index = j;}}// 2、prim三部曲，第二步：最近節點（index）加入生成樹v[index] = true;//加入到最小生成樹中// 3、prim三部曲，第三步：更新非生成樹節點到生成樹的距離（即更新ans數組）// indx節點加入之后， 最小生成樹加入了新的節點，那么所有節點到 最小生成樹的距離（即ans數組）需要更新一下// 由于index節點是新加入到最小生成樹，那么只需要關心與 index 相連的 非生成樹節點 的距離 是否比 原來 非生成樹節點到生成樹節點的距離更小了呢for(int j=1;j<=n;j++){if(!v[j] && e[index][j] < ans[j]) ans[j] = e[index][j];}}for(int i=2;i<=n;i++) res += ans[i];cout<<res<<endl;
}signed main()
{IOSint T=1;pre_handle();
// cin>>T;while(T--) solve(); return 0;
}
注意最后從2到n累加? 因為遍歷了n-1此只需要統計n-1條邊即可，1是起點，ans[1]還是初始最大值?
| 特性 | 鄰接矩陣版 | 鄰接表+優先隊列版 |
|---|---|---|
| 時間復雜度 | O(V2) | O(Elog?V) |
| 適用場景 | 稠密圖（E≈V2） | 稀疏圖（E?V2） |
| 空間復雜度 | O(V2) | O(V+E) |
| 是否需要堆 | 否 | 是 |
根據題目數據范圍選擇即可，建議兩者均保存為模板備用。
?kruskal算法
kruskal算法和prim算法解決的是同一個問題，兩者區別在于prim算法是以點構建最小生成樹的，而kruskal算法則是通過邊和邊構成最小生成樹的，詳細區別如下：
| 特性 | Kruskal算法 | Prim算法 |
|---|---|---|
| 核心思想 | 貪心+并查集，按邊權排序從小到大選邊 | 貪心+優先隊列/鄰接矩陣，從點擴展 MST |
| 時間復雜度 | O(Elog?E)（排序占主導） | 鄰接表+堆：O(Elog?V) 鄰接矩陣：O(V2) |
| 適用存儲結構 | 邊集數組（適合稀疏圖） | 鄰接表（稀疏圖）或鄰接矩陣（稠密圖） |
| 是否需要處理連通性 | 需用并查集判斷是否成環 | 自動處理連通性（通過點的集合擴展） |
| 優勢場景 | 稀疏圖（E?V2） | 稠密圖（E≈V2） |
個人感覺kruskal算法還是比prim好理解一點的，只需要將最小生成樹抽象為一個集合然后用并查集對兩個節點是否在最小生成樹中進行查詢即可！是不是很容易理解呢？對并查集不熟悉的小伙伴可以看主播的上一篇博客喲~
尋寶的kruskal解法
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;
int n,m;
vector<int> tree(N);//并查集數組
void init()//初始化并查集數組
{for(int i=1;i<=n;i++) tree[i] = i;
}
int find(int x)//并查集查找函數
{if(x == tree[x]) return x;return tree[x] = find(tree[x]);
}
void join(int x,int y)
{x = find(x);y = find(y);if(x == y) return ;tree[x] = y;
}
bool is(int x,int y)
{x = find(x);y = find(y);return x==y ? true : false;
}
struct edge
{int u,v,x;
};
vector<edge> e;
bool cmp(const edge& x, const edge& y)//提升排序效率！
{return x.x < y.x;
}
void solve()
{cin>>n>>m;init();for(int i=1;i<=m;i++){int u,v,x;cin>>u>>v>>x;e.push_back({u,v,x});}sort(e.begin(),e.end(),cmp);//對邊權進行排序int res=0;for(auto i : e){if(!is(i.u,i.v)){join(i.u,i.v);res += i.x;}else continue;//可加可不加}cout<<res<<endl;
}signed main()
{IOSint T=1;
// cin>>T;while(T--) solve(); return 0;
}
kruscal的思路：
- 邊的權值排序，因為要優先選最小的邊加入到生成樹里
- 遍歷排序后的邊
- 如果邊首尾的兩個節點在同一個集合，說明如果連上這條邊圖中會出現環
- 如果邊首尾的兩個節點不在同一個集合，加入到最小生成樹，并把兩個節點加入同一個集合
kruskal模板?
最小生成樹kruskal算法的模板：ICPCer可拿 ！
#include <bits/stdc++.h>
using namespace std;
#define int long long // 使用long long類型
#define endl '\n' // 換行符
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) // 加速輸入輸出
#define pii pair<int,int> // 簡寫pair類型
#define fi first // 簡寫pair的first
#define se second // 簡寫pair的second
const int inf = 0x3f3f3f3f; // 定義無窮大
const int N = 1e5+10; // 最大節點數，根據題目調整int n,m; // n:節點數 m:邊數
vector<int> tree(N); // 并查集數組// 初始化并查集
void init()
{for(int i=1;i<=n;i++) tree[i]=i; // 每個節點初始父節點是自己
}// 查找根節點（帶路徑壓縮）
int find(int x)
{if(x == tree[x]) return x; // 找到根節點return tree[x] = find(tree[x]); // 路徑壓縮
}// 合并兩個集合
void join(int x,int y)
{x = find(x); // 找到x的根y = find(y); // 找到y的根if(x == y) return; // 已經在同一集合tree[x] = y; // 合并集合
}// 判斷兩個節點是否在同一集合
bool isSame(int x, int y)
{return find(x) == find(y);
}// 邊結構體
struct edge
{int u, v, w; // u:起點 v:終點 w:邊權
};vector<edge> e; // 存儲所有邊// 邊權比較函數（用于排序）
bool cmp(const edge& x, const edge& y)
{return x.w < y.w; // 按邊權從小到大排序
}void solve()
{cin>>n>>m; // 輸入節點數和邊數init(); // 初始化并查集e.clear(); // 清空邊集（多組數據時很重要）// 輸入所有邊for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e.push_back({u,v,w}); // 存儲邊}sort(e.begin(),e.end(),cmp); // 按邊權排序int res=0,cnt=0; // res:最小生成樹權值和 cnt:已選邊數for(auto& i : e){if(!isSame(i.u,i.v)) // 如果邊的兩個端點不在同一集合{join(i.u,i.v); // 合并集合res += i.w; // 累加邊權cnt++; // 邊數增加if(cnt == n-1) break; // 已選夠n-1條邊，提前退出}}// 輸出結果（如果不能形成生成樹輸出-1）cout<<(cnt == n-1 ? res : -1)<<endl;
}signed main()
{IOS; // 加速輸入輸出int T = 1;// cin >> T; // 多組數據時取消注釋while(T--) solve();return 0;
}?總結
此時我們已經講完了 Kruskal 和 prim 兩個解法來求最小生成樹。
什么情況用哪個算法更合適呢。
Kruskal 與 prim 的關鍵區別在于，prim維護的是節點的集合，而 Kruskal 維護的是邊的集合。 如果 一個圖中，節點多，但邊相對較少，那么使用Kruskal 更優。
為什么邊少的話，使用 Kruskal 更優呢？
因為 Kruskal 是對邊進行排序的后 進行操作是否加入到最小生成樹。
邊如果少，那么遍歷操作的次數就少。
在節點數量固定的情況下，圖中的邊越少，Kruskal 需要遍歷的邊也就越少。
而 prim 算法是對節點進行操作的，節點數量越少，prim算法效率就越優。
所以在 稀疏圖中，用Kruskal更優。 在稠密圖中，用prim算法更優。
邊數量較少為稀疏圖，接近或等于完全圖（所有節點皆相連）為稠密圖
Prim 算法 時間復雜度為 O(n^2)，其中 n 為節點數量，它的運行效率和圖中邊樹無關，適用稠密圖。
Kruskal算法 時間復雜度 為 nlogn，其中n 為邊的數量，適用稀疏圖。
 視頻教程 - 微博文章數據可視化分析-點贊區間實現)
