图论：最小生成树

今天要介绍两中最小生成树的算法，分别是prim算法和kruskal算法。

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。

那么如何选择这n-1条边就是最小生成树算法的任务所在。

prim算法：

prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。prim算法核心就是以下三步：

1. 第一步，选距离生成树最近非生成树节点
2. 第二步，最近节点加入生成树
3. 第三步，更新非生成树节点到生成树的距离（即更新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(V²)	O(Elog⁡V)
适用场景	稠密图（E≈V²）	稀疏图（E≪V²）
空间复杂度	O(V²)	O(V+E)
是否需要堆	否	是

根据题目数据范围选择即可，建议两者均保存为模板备用。

 kruskal算法

kruskal算法和prim算法解决的是同一个问题，两者区别在于prim算法是以点构建最小生成树的，而kruskal算法则是通过边和边构成最小生成树的，详细区别如下：

特性	Kruskal算法	Prim算法
核心思想	贪心+并查集，按边权排序从小到大选边	贪心+优先队列/邻接矩阵，从点扩展 MST
时间复杂度	O(Elog⁡E)（排序占主导）	邻接表+堆：O(Elog⁡V) 邻接矩阵：O(V²)
适用存储结构	边集数组（适合稀疏图）	邻接表（稀疏图）或邻接矩阵（稠密图）
是否需要处理连通性	需用并查集判断是否成环	自动处理连通性（通过点的集合扩展）
优势场景	稀疏图（E≪V²）	稠密图（E≈V²）

个人感觉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 为边的数量，适用稀疏图。