🔥keyipatience:个人主页
🎬作者简介：C/C++后端开发学习者
🌟专栏传送门：《c++》《linux》《c++高阶数据结构》《c++数据结构与算法》
⭐️patience is key in life
前提知识
2者都是用来求【无向连通图】的最小生成树（MST）
有向图不存在最小生成树，只有最小树形图，下面实现的2种算法都是以前面的邻接矩阵实现
Kruskal算法
核心：所有边一次性全部入 vector 排序或者优先级队列，用并查集判环
优先级队列版本：
核心思路
- 把所有边放进小根堆，按权重从小到大拿边
- 每次取出当前权重最小的边
- 并查集：两个顶点不在同一集合 → 选这条边，合并集合；在同一集合 → 跳过（会形成环）
- 选出
n-1条边就停止，得到最小生成树
一步步实现优先级队列版本Kruskal代码
1.准备工作（Edge 结构体）
struct Edge { int _srci; //起点下标 int _dsti; //终点下标 W _w; //边权重 Edge(int srci, int dsti, const W& w) :_srci(srci), _dsti(dsti), _w(w) {} bool operator>(const Edge&e)const { return _w > e._w;//为true则_w的优先级低，低的优先级在下面又_w大，则小的在上面为小根堆 } };重载>是为了greater<Edge>，实现小根堆：权重小的边优先弹出。
2.初始化最小生成树 minTree
int n = _vertexs.size(); minTree._vertexs = _vertexs; minTree._indexmap = _indexmap; minTree._matrix.assign(n, vector<W>(n, MAX_W));- minTree 是用来保存最后生成树的图对象
- 顶点列表、顶点下标映射和原图完全一样
- 邻接矩阵全部初始化为最大值（代表没有边）
3.把原图所有边放进小根堆（去重！i<j）
priority_queue<Edge,vector<Edge>,greater<Edge> >minque; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i<j && _matrix[i][j] != MAX_W) { minque.push(Edge(i, j, _matrix[i][j])); } } }- 无向图邻接矩阵对称：
matrix[i][j] = matrix[j][i] i<j：只取一次边，防止同一条边重复入堆，重复入了结果答案不会错，但是堆里面边数量翻倍，堆排序 / 弹出耗时变多，效率下降。- 条件
_matrix[i][j] != MAX_W：跳过不存在的边 - 全部入堆之后：堆顶永远是当前权重最小的边
等价操作：把所有边放到数组，
sort从小到大排序。堆只是另一种取最小的方式。
4.循环取出最小边，判断、选择
int size = 0; //已经选进生成树的边数量 W totalW = W(); //总权重 UnionFindSet ufs(n); //并查集，n个顶点，每个点初始自己是一个集合 while (!minque.empty()) { Edge min = minque.top(); //拿权重最小边 minque.pop(); //弹出堆 // 判断两个点是否不在同一集合（不会形成环） if (!ufs.InSet(min._srci, min._dsti)) { // 1.打印这条选中的边 cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] <<"-"<< min._w << endl; // 2.把这条边加入最小生成树minTree minTree._AddEdge(min._srci, min._dsti, min._w); // 3.合并两个顶点所在集合 ufs.Union(min._srci, min._dsti); // 4.计数+1，累加总权重 size++; totalW += min._w; // 选够 n-1 条边，最小生成树已经完成，直接break if(size == n-1) break; } }单次循环拆解
- 取堆顶最小边，弹出
- 并查集查询：两点是否连通 不连通：选中这条边，加入生成树，并查集合并集合，计数 + 1 已经连通：放弃这条边（会构成环），直接下一轮
- 一旦选中边数量等于
n-1：立刻跳出循环。
n 个顶点的生成树，固定就是 n-1 条边，再多就必然有环。
整体代码：
typedef Graph<V, W, MAX_W, Direction> Self; struct Edge { int _srci; int _dsti; W _w; Edge(int srci, int dsti, const W& w) :_srci(srci) , _dsti(dsti) , _w(w) {} bool operator>(const Edge&e)const//重载greater即> { return _w > e._w;//为真e1大，优先级低在下面，e2小的在上面，为小堆 } }; W Kruskal(Self& minTree) { int n = _vertexs.size(); minTree._vertexs = _vertexs;//也必须要有n个顶点和原图得保持一样 minTree._indexmap = _indexmap;//映射关系也一样 //上面2个都是和原图一样的，只有_matrix不一样，即点与点的连接方式不一样 minTree._matrix.assign(n, vector<W>(n, MAX_W)); priority_queue<Edge,vector<Edge>,greater<Edge> >minque;//大堆less，小堆greater //把所有边全部入优先级队列，拍好序，和用sort一样 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i<j&&_matrix[i][j] != MAX_W)//无向图不用重复入同一条边重复存入 edges 数组 2 //次排序后 Kruskal 会重复处理这条边，白白浪费时间，虽然并查集能过滤掉，但是边数量翻倍，低效。 { minque.push(Edge(i, j, _matrix[i][j])); } } } int size = 0;//选出n-1条边 W totalW = W(); UnionFindSet ufs(n);//默认初始化n个值全为-1 while (!minque.empty()) { Edge min = minque.top(); minque.pop(); if (!ufs.InSet(min._srci, min._dsti))//不在一个集合 { cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] <<"-"<< min._w << endl;//打印每一次选的边 minTree._AddEdge(min._srci, min._dsti, min._w);//添加一条边 ufs.Union(min._srci, min._dsti);//添加到并查集 size++; totalW += min._w; if(size == n-1) break; } } return totalW； }sort排序版本（更适用）
typedef Graph<V, W, MAX_W, Direction> Self; struct Edge { int _srci; int _dsti; W _w; Edge(int srci, int dsti, const W& w) :_srci(srci) , _dsti(dsti) , _w(w) {} bool operator>(const Edge&e)const//重载greater即>优先级队列用 { return _w >e._w;//为真_w大，优先级低在下面，小的在上面，为小堆 } bool operator<(const Edge& e)const//sort默认用less { return _w < e._w;//为真_w小，优先级高在前面，升序 } }; W Kruskal(Self& minTree) { int n = _vertexs.size(); minTree._vertexs = _vertexs;//也必须要有n个顶点和原图得保持一样 minTree._indexmap = _indexmap;//映射关系也一样 //上面2个都是和原图一样的，只有_matrix不一样，即点与点的连接方式不一样 minTree._matrix.assign(n, vector<W>(n, MAX_W)); // ========== 改动开始 ========== vector<Edge>edges; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i<j&&_matrix[i][j] != MAX_W)//无向图不用重复入，同一条边重复存入 edges 数组 //2 次排序后 Kruskal 会重复处理这条边，白白浪费时间，虽然并查集能过滤掉，但是边数量翻倍，低效。 { edges.emplace_back(Edge(i, j, _matrix[i][j])); } } } // 从小到大排序！ sort(edges.begin(), edges.end()); int size = 0;//选出n-1条边 W totalW = W(); UnionFindSet ufs(n);//默认初始化n个值全为-1 for (auto& min : edges) { if (!ufs.InSet(min._srci, min._dsti)) { cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << "-" << min._w << endl;//打印每一次选的边 minTree._AddEdge(min._srci, min._dsti, min._w); ufs.Union(min._srci, min._dsti); size++; totalW += min._w; if (size == n - 1) break; // 选够n-1条边，直接退出，优化 } } return totalW; }测试实例：
void TestGraphMinTree() { const char* str = "abcdefghi"; Graph<char, int,INT_MAX> g(str, strlen(str)); g.AddEdge('a', 'b', 4); g.AddEdge('a', 'h', 8); g.AddEdge('b', 'c', 8); g.AddEdge('b', 'h', 11); g.AddEdge('c', 'i', 2); g.AddEdge('c', 'f', 4); g.AddEdge('c', 'd', 7); g.AddEdge('d', 'f', 14); g.AddEdge('d', 'e', 9); g.AddEdge('e', 'f', 10); g.AddEdge('f', 'g', 2); g.AddEdge('g', 'h', 1); g.AddEdge('g', 'i', 6); g.AddEdge('h', 'i', 7); Graph<char, int,INT_MAX> kminTree; cout << "Kruskal:" << g.Kruskal(kminTree) << endl; kminTree.Print(); /*Graph<char, int,INT_MAX> pminTree; cout << "Prim:" << g.Prim(pminTree, 'a') << endl; pminTree.Print();*/ }2种方法结果一样：
Prim算法（堆优化版)
核心思想：维护一个已经选入生成树的点集合 S，每次从「S 里的点连向 S 外面的点」所有边中挑权重最小的那条边，把新点拉进 S，直到所有点都进来。即选一个点开始一边动态入堆，S数组标记点，不用并查集
一步步实现Prim算法代码：
配套结构体：还是之前的 Edge
struct Edge { int _srci; int _dsti; W _w; Edge(int srci, int dsti, const W& w) :_srci(srci), _dsti(dsti), _w(w) {} bool operator>(const Edge&e)const { return _w > e._w; } };1.初始化最小生成树 minTree
minTree._vertexs = _vertexs; minTree._indexmap = _indexmap; minTree._matrix.assign(n, vector<W>(n, MAX_W));2.起点入集合，起点相连边全部入堆
vis[srci] = true; for (int i = 0; i < n; i++) { if (_matrix[srci][i] != MAX_W) { minq.push(Edge(srci, i, _matrix[srci][i])); } }- 起点 src 标记为已访问，直接加入集合 S
- 遍历邻接矩阵，把起点所有存在的边，全部放进小根堆
和 Kruskal 最大区别：Kruskal 一开始一次性把整张图所有边入堆；Prim 只把 S 向外的边入堆，边是动态添加
3.循环取最小候选边并动态添加新边
while (!minq.empty()) { Edge min = minq.top(); minq.pop(); if (!vis[min._dsti]) { //选中这条边 cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << "-" << min._w << endl; minTree._AddEdge(min._srci, min._dsti, min._w); vis[min._dsti] = true; size++; totalW += min._w; if (size == n - 1)break; //新点向外的边入堆 for (int i = 0; i < n; i++) { if (_matrix[min._dsti][i] != MAX_W && !vis[i]) { minq.push(Edge(min._dsti, i, _matrix[min._dsti][i])); } } } }单次循环拆解：
- 取出堆顶权重最小边，弹出堆
- 判断边终点
min._dsti：!vis[min._dsti]：终点不在 S 集合，可以选这条边
- 边加入生成树 minTree
- 标记终点
vis=true，拉入集合 S - 边计数 size+1，权重累加
- 如果已经选够 n-1 条边，直接退出循环，生成树完成
- 把刚加入 S 的这个新点，所有连向 S 外面点的边，压入堆（新增候选边）
vis[min._dsti]==true：终点已经在 S 集合内，这条边是集合内部的边，选了会形成环 → 直接丢弃这条边，继续下一轮
完整代码：
W Prim(Self &minTree,int src) { int srci = GetVertexIndex(src); int n = _vertexs.size(); int size = 0; W totalW = W(); minTree._vertexs = _vertexs;//也必须要有n个顶点和原图得保持一样 minTree._indexmap = _indexmap;//映射关系也一样 minTree._matrix.assign(n, vector<W>(n, MAX_W)); vector<bool>vis(n,false); priority_queue<Edge, vector<Edge>, greater<Edge> >minq; vis[srci] = true； //先把与srci连接的边加到队列中 for (int i = 0; i < n; i++) { if (_matrix[srci][i] != MAX_W) { minq.push(Edge(srci, i, _matrix[srci][i])); } } //开始选边 while (!minq.empty()) { Edge min = minq.top(); minq.pop(); if (!vis[min._dsti]) { cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << "-" << min._w << endl; minTree._AddEdge(min._srci, min._dsti, min._w); vis[min._dsti] = true; size++; totalW += min._w; if (size == n - 1)break; //接着往外添加边到minq for (int i = 0; i < n; i++) { if (_matrix[min._dsti][i] != MAX_W && !vis[i]) { minq.push(Edge(min._dsti, i, _matrix[min._dsti][i])); } } } } return totalW; }测试实例：
void TestGraphMinTree() { const char* str = "abcdefghi"; Graph<char, int,INT_MAX> g(str, strlen(str)); g.AddEdge('a', 'b', 4); g.AddEdge('a', 'h', 8); g.AddEdge('b', 'c', 8); g.AddEdge('b', 'h', 11); g.AddEdge('c', 'i', 2); g.AddEdge('c', 'f', 4); g.AddEdge('c', 'd', 7); g.AddEdge('d', 'f', 14); g.AddEdge('d', 'e', 9); g.AddEdge('e', 'f', 10); g.AddEdge('f', 'g', 2); g.AddEdge('g', 'h', 1); g.AddEdge('g', 'i', 6); g.AddEdge('h', 'i', 7); /*Graph<char, int,INT_MAX> kminTree; cout << "Kruskal:" << g.Kruskal(kminTree) << endl; kminTree.Print();*/ Graph<char,int,INT_MAX> pminTree; cout << "Prim:" << g.Prim(pminTree, 'a') << endl;//以a为起点 pminTree.Print(); }运行结果：
Kruskal vs 堆 Prim对比
- Kruskal：一次性收集全部边，放进 vector 排序（也可以全部丢进优先队列）。 逻辑：全局所有边，从小到大挨个选；用并查集判断会不会形成环。
- 堆优化 Prim：从一个起点出发。 取出一条合法边、纳入新点之后，再把这个新点的邻边陆续压入堆，边是动态入堆，不是一次性全部放进去；用
vis标记点是否已经加入生成树。
| Prim (堆优化) | Kruskal |
|---|---|
| 选点 | 选边 |
| 维护点集合 S，vis 数组标记 | 维护连通分量，并查集判环 |
| 适合稠密图（点少边多） | 适合稀疏图（边少） |
| 时间复杂度 O(ElogE)（E:边数） | 时间复杂度 O(ElogE) |
| 需要指定起点 | 不需要起点 |
