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 Edgee)const { return _w e._w;//为true则_w的优先级低低的优先级在下面又_w大则小的在上面为小根堆 } };重载是为了greaterEdge实现小根堆权重小的边优先弹出。2.初始化最小生成树 minTreeint n _vertexs.size(); minTree._vertexs _vertexs; minTree._indexmap _indexmap; minTree._matrix.assign(n, vectorW(n, MAX_W));minTree 是用来保存最后生成树的图对象顶点列表、顶点下标映射和原图完全一样邻接矩阵全部初始化为最大值代表没有边3.把原图所有边放进小根堆去重ijpriority_queueEdge,vectorEdge,greaterEdge minque; for (int i 0; i n; i) { for (int j 0; j n; j) { if (ij _matrix[i][j] ! MAX_W) { minque.push(Edge(i, j, _matrix[i][j])); } } }无向图邻接矩阵对称matrix[i][j] matrix[j][i]ij只取一次边防止同一条边重复入堆重复入了结果答案不会错但是堆里面边数量翻倍堆排序 / 弹出耗时变多效率下降。条件_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 GraphV, 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 Edgee)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, vectorW(n, MAX_W)); priority_queueEdge,vectorEdge,greaterEdge minque;//大堆less小堆greater //把所有边全部入优先级队列拍好序和用sort一样 for (int i 0; i n; i) { for (int j 0; j n; j) { if (ij_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 GraphV, 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 Edgee)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, vectorW(n, MAX_W)); // 改动开始 vectorEdgeedges; for (int i 0; i n; i) { for (int j 0; j n; j) { if (ij_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; Graphchar, 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); Graphchar, int,INT_MAX kminTree; cout Kruskal: g.Kruskal(kminTree) endl; kminTree.Print(); /*Graphchar, int,INT_MAX pminTree; cout Prim: g.Prim(pminTree, a) endl; pminTree.Print();*/ }2种方法结果一样Prim算法堆优化版)核心思想维护一个已经选入生成树的点集合 S每次从「S 里的点连向 S 外面的点」所有边中挑权重最小的那条边把新点拉进 S直到所有点都进来。即选一个点开始一边动态入堆S数组标记点不用并查集一步步实现Prim算法代码配套结构体还是之前的 Edgestruct Edge { int _srci; int _dsti; W _w; Edge(int srci, int dsti, const W w) :_srci(srci), _dsti(dsti), _w(w) {} bool operator(const Edgee)const { return _w e._w; } };1.初始化最小生成树 minTreeminTree._vertexs _vertexs; minTree._indexmap _indexmap; minTree._matrix.assign(n, vectorW(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标记终点vistrue拉入集合 S边计数 size1权重累加如果已经选够 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, vectorW(n, MAX_W)); vectorboolvis(n,false); priority_queueEdge, vectorEdge, greaterEdge 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; Graphchar, 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); /*Graphchar, int,INT_MAX kminTree; cout Kruskal: g.Kruskal(kminTree) endl; kminTree.Print();*/ Graphchar,int,INT_MAX pminTree; cout Prim: g.Prim(pminTree, a) endl;//以a为起点 pminTree.Print(); }运行结果Kruskal vs 堆 Prim对比Kruskal一次性收集全部边放进 vector 排序也可以全部丢进优先队列。 逻辑全局所有边从小到大挨个选用并查集判断会不会形成环。堆优化 Prim从一个起点出发。 取出一条合法边、纳入新点之后再把这个新点的邻边陆续压入堆边是动态入堆不是一次性全部放进去用vis标记点是否已经加入生成树。Prim (堆优化)Kruskal选点选边维护点集合 Svis 数组标记维护连通分量并查集判环适合稠密图点少边多适合稀疏图边少时间复杂度 O(ElogE)E:边数时间复杂度 O(ElogE)需要指定起点不需要起点