发布时间：2025-06-24 20:10:22  作者：北方职教升学中心  阅读量：256

我们今天就来介绍一下这两种算法：

Kruskal算法

Kruskal算法，简单来说，就是把所有边拿出来，从小到大挑边，构成最小生成树：

Kruskal算法是一种用于寻找加权、无向连通图的最小生成树（Minimum Spanning Tree, MST）的贪心算法。

它的边的总权重是所有可能生成树中最小的。如果不是，将这条边添加到最小生成树中，并将这两个顶点所在的树合并成一棵更大的树。

它是一个没有环的连通子图（即树）。对于每条边，检查它的两个端点是否已经在同一棵树中（即是否属于同一个连通分量）。

Kruskal算法的关键在于能够快速地检测边的两个端点是否属于同一棵树，这通常是通过使用并查集（Union-Find）数据结构来实现的。它的核心思想是在不形成任何环路的情况下，选择权重最小的边来构建生成树，直到所有的顶点都被包含在树中。无向的连通图中，由所有顶点构成的一个子图，这个子图是一棵树，并且其所有边的权重之和最小。

最小生成树具有以下特性：

1. 它包含图中的所有顶点。

   数据结构 —— 最小生成树

   • 什么是最小生成树
   • Kruskal算法
   • Prim算法

   今天我们来看一下最小生成树：

   我们之前学习的遍历算法并没有考虑权值，仅仅就是遍历结点：
   今天的最小生成树要满足几个条件：

   1. 考虑权值
   2. 所有结点联通
   3. 权值之和最小
   4. 无环

   

   什么是最小生成树

   最小生成树（Minimum Spanning Tree，简称MST）是指在一个加权的、

   Prim算法基本步骤：

   1. 选择任意一个顶点作为起始顶点。换句话说，最小生成树是在保证图中所有顶点连通的前提下，使得连接这些顶点的边的总成本最低的一棵树。

   最小生成树在很多实际应用中都有重要作用，例如在设计电信网络时，为了连接多个地点而需要铺设电缆或光纤，最小生成树可以用来确定一种成本最低的铺设方案。

   Prim算法

   Prim算法和上面的思想差不多，但是，Prim算法会从一个顶点开始，这里我假设是从"小潮"开始：
   
   跟小潮连接的3条边，会进入优先级队列，维护起来：
   接下来，会选择30的权重来构造，然后30这条边的另一边的小傲的边入优先级队列：
   
   以此类推：

   // 使用Prim算法构建并返回最小生成树的总权重W Prim(Self&minTree,constV&vertex)// Self应该是当前类的引用，minTree是用于存储最小生成树的实例，vertex是顶点的容器{// 初始化最小生成树的顶点集和索引minTree._vertex =_vertex;minTree._index =_index;minTree._matrix.resize(_vertex.size());// 创建一个邻接矩阵，用于存储最小生成树中的边的权重// 初始化邻接矩阵的所有元素为最大权重值MAX_Wfor(auto&e :minTree._matrix){e.resize(_vertex.size(),MAX_W);}// 区分顶点集合：已选择和未选择size_t srcIndex =FindSrci(vertex);// 找到起始顶点的索引vector<bool>select(_vertex.size(),false);// 已选择顶点集合，初始时所有顶点都未选择vector<bool>non_select(_vertex.size(),true);// 未选择顶点集合，初始时所有顶点都未被选择select[srcIndex]=true;// 起始顶点被标记为已选择non_select[srcIndex]=false;// 起始顶点从未选择集合中移除// 创建一个优先级队列，用于存储待处理的边priority_queue<Edge,vector<Edge>,greater<Edge>>pq;// 边按权重从小到大排序// 将起始顶点的邻接边加入优先级队列for(inti =0;i <_vertex.size();i++){if(_matrix[srcIndex][i]!=MAX_W)// 如果存在边，且不是最大权重（表示边存在）{pq.push(Edge(srcIndex,i,_matrix[srcIndex][i]));// 加入边信息到优先级队列}}// 初始化计数器和总权重size_t size =0;W total =W();// 初始化总权重为0// 当优先级队列非空时while(!pq.empty()){Edge min =pq.top();// 获取当前权重最小的边pq.pop();// 从队列中移除已处理的边// 如果目标顶点已被选择，跳过这条边if(select[min._desi])continue;// 输出边的信息cout <<_vertex[min._srci]<<"-"<<_vertex[min._desi]<<":"<<_matrix[min._srci][min._desi]<<endl;// 添加边到最小生成树minTree._AddEdge(min._srci,min._desi,min._w);// 标记目标顶点为已选择select[min._desi]=true;non_select[min._desi]=false;++size;// 已处理的边数量加1total +=min._w;// 更新总权重// 将新加入顶点的邻接边加入优先级队列for(size_t i =0;i <_vertex.size();i++){if(_matrix[min._desi][i]!=MAX_W &&non_select[i])// 如果存在边且目标顶点未被选择{pq.push(Edge(min._desi,i,_matrix[min._desi][i]));// 加入边信息到优先级队列}}}// 打印最小生成树minTree.Print();// 如果边的数量等于顶点数量减一，则返回最小生成树的总权重if(size ==_vertex.size()-1){returntotal;}else{returnW();// 否则返回默认权重值（可能表示无法形成最小生成树）}}

   voidTestGraph2(){string a[]={"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};Graph<string,int,INT_MAX,false>g1(a,sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮","小傲",30);g1.AddEdge("小潮","高斯",83);g1.AddEdge("小潮","海皇",34);g1.AddEdge("胖迪","海皇",78);g1.AddEdge("胖迪","小傲",76);g1.AddEdge("小杨","皖皖",54);g1.AddEdge("小杨","高斯",48);g1.Print();cout <<endl;Graph<string,int,INT_MAX,false>kminTree;cout <<"Kruskal:"<<g1.Kruskal(kminTree)<<endl;cout <<endl;Graph<string,int,INT_MAX,false>pminTree;cout <<"Prim:"<<g1.Prim(pminTree,"小潮")<<endl;}

   

   Prim算法同样是用于寻找加权无向图的最小生成树(Minimum Spanning Tree, MST)的一种贪心算法。

   以下是Kruskal算法的主要步骤：

   1. 排序边：将图中所有的边按照权重从小到大排序。Prim算法可以使用优先队列（Priority Queue）来高效地选择下一个应加入的边。
   2. 在当前树的顶点的邻接边中找到权重最小的边，将这条边添加到树中，并将新的顶点也添加进来。在最好的情况下，排序边的时间复杂度为O(E log E)，其中E是边的数量；并查集操作的时间复杂度接近常数，因此整个算法的时间复杂度近似为O(E log E)。

      求解最小生成树的常用算法包括：

      • Kruskal算法：此算法通过不断选择权重最小的边来构建最小生成树，同时避免添加会导致环路形成的边。
      • Prim算法：此算法从任意一个顶点开始，逐步将顶点及其权重最小的连接边加入到生成树中，直到所有顶点都被包含进来。

   这是两种算法挑选边的过程和最后结果，大家可以类比对比：

   //Kruskal算法W Kruskal(Self&minTree){//初始化minTree._vertex =_vertex;minTree._index =_index;minTree._matrix.resize(_vertex.size());for(auto&e :minTree._matrix){e.resize(_vertex.size(),MAX_W);}//优先级队列priority_queue<Edge,vector<Edge>,greater<Edge>>pq;for(size_t i =0;i <_vertex.size();i++){for(size_t j =0;j <_vertex.size();j++){if(i <j &&_matrix[i][j]!=MAX_W){pq.push(Edge(i,j,_matrix[i][j]));}}}//拿边构造最小生成树W totoal =W();intsize =0;UnionFindSet ufs(_vertex.size());while(!pq.empty()){Edge min =pq.top();//出边pq.pop();//判断是否在同一集合if(!ufs.InSet(min._srci ,min._desi)){cout <<_vertex[min._srci]<<"-"<<_vertex[min._desi]<<":"<<_matrix[min._srci][min._desi]<<endl;minTree._AddEdge(min._srci,min._desi,min._w);totoal +=min._w;//合并ufs.Union(min._srci,min._desi);++size;}}cout <<endl;minTree.Print();if(size ==_vertex.size()-1){returntotoal;}else{returnW();}}W Prim(Self&minTree,constV&vertex){//初始化minTree._vertex =_vertex;minTree._index =_index;minTree._matrix.resize(_vertex.size());for(auto&e :minTree._matrix){e.resize(_vertex.size(),MAX_W);}//区分集合size_t srcIndex =FindSrci(vertex);vector<bool>select(_vertex.size(),false);vector<bool>non_select(_vertex.size(),true);select[srcIndex]=true;non_select[srcIndex]=false;//开始入边priority_queue<Edge,vector<Edge>,greater<Edge>>pq;for(inti =0;i <_vertex.size();i++){if(_matrix[srcIndex][i]!=MAX_W){pq.push(Edge(srcIndex,i,_matrix[srcIndex][i]));}}size_t size =0;W totoal =W();while(!pq.empty()){Edge min =pq.top();pq.pop();if(select[min._desi])continue;cout <<_vertex[min._srci]<<"-"<<_vertex[min._desi]<<":"<<_matrix[min._srci][min._desi]<<endl;minTree._AddEdge(min._srci,min._desi,min._w);select[min._desi]=true;non_select[min._desi]=false;++size;totoal +=min._w;//新入的顶点的边也加入到优先级队列for(size_t i =0;i <_vertex.size();i++){if(_matrix[min._desi][i]!=MAX_W &&non_select[i]){pq.push(Edge(min._desi,i,_matrix[min._desi][i]));}}}minTree.Print();if(size ==_vertex.size()-1){returntotoal;}else{returnW();}}

   

   与Kruskal算法不同的是，Prim算法从一个顶点开始，逐步添加最短的边来扩展树，直到包含所有的顶点。并查集允许我们在对数时间内执行“查找”操作（确定顶点所属的树）和“合并”操作（将两棵树合并成一棵树）。
2. 选择边：遍历排序后的边列表。
3. 它的边数比顶点数少一（对于 n 个顶点的图，有 n-1 条边）。
4. 初始化森林：创建一个森林，其中每个顶点都是一个单独的树（即每个顶点都是一个独立的连通分量）。
5. 重复步骤3：继续选择满足条件的边，直到最小生成树中包含了图中的所有顶点，或者已经选择了n-1条边（其中n是顶点的数量）。它通常利用并查集（Disjoint Set Union）数据结构来检测环路。
6. 重复步骤2，直到树包含所有的顶点。由于排序的主导作用，该算法适用于边的数量远小于顶点数量平方的图，即稀疏图。

   // 使用Kruskal算法计算最小生成树的总权重W Kruskal(Self&minTree)// Self应为当前类的引用，minTree是用于存储最小生成树的实例{// 初始化最小生成树的顶点集和索引minTree._vertex =_vertex;minTree._index =_index;minTree._matrix.resize(_vertex.size());// 创建一个邻接矩阵，用于存储最小生成树中的边的权重for(auto&e :minTree._matrix)// 将邻接矩阵的所有元素初始化为最大权重值MAX_W{e.resize(_vertex.size(),MAX_W);}// 创建一个优先级队列，用于存储边的信息priority_queue<Edge,vector<Edge>,greater<Edge>>pq;// 将所有边（除了自环和重复边）加入优先级队列for(size_t i =0;i <_vertex.size();i++){for(size_t j =0;j <_vertex.size();j++){if(i <j &&_matrix[i][j]!=MAX_W)// 确保不加入自环和重复边{pq.push(Edge(i,j,_matrix[i][j]));// 将边加入优先级队列}}}// 初始化变量，用于记录最小生成树的总权重和边的数量W total =W();intsize =0;UnionFindSet ufs(_vertex.size());// 创建并查集，用于判断顶点是否已经连接while(!pq.empty())// 当优先级队列非空时{Edge min =pq.top();// 取出权重最小的边pq.pop();// 移除已取出的边// 判断边的两个顶点是否已经在同一集合内（即是否已经连接）if(!ufs.InSet(min._srci,min._desi)){cout <<_vertex[min._srci]<<"-"<<_vertex[min._desi]<<":"<<_matrix[min._srci][min._desi]<<endl;// 打印边的信息minTree._AddEdge(min._srci,min._desi,min._w);// 将边加入最小生成树total +=min._w;// 更新最小生成树的总权重ufs.Union(min._srci,min._desi);// 合并两个顶点所在的集合++size;// 增加边的数量}}cout <<endl;minTree.Print();// 打印最小生成树// 如果边的数量等于顶点数量减一，则返回最小生成树的总权重if(size ==_vertex.size()-1){returntotal;}else{returnW();// 否则返回默认权重值（可能表示无法形成最小生成树）}}

   我们可以来测试一下：

   voidTestGraph2(){string a[]={"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};Graph<string,int,INT_MAX,false>g1(a,sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮","小傲",30);g1.AddEdge("小潮","高斯",83);g1.AddEdge("小潮","海皇",34);g1.AddEdge("胖迪","海皇",78);g1.AddEdge("胖迪","小傲",76);g1.AddEdge("小杨","皖皖",54);g1.AddEdge("小杨","高斯",48);g1.Print();cout <<endl;Graph<string,int,INT_MAX,false>kminTree;cout <<"Kruskal:"<<g1.Kruskal(kminTree)<<endl;}

   按照Kruskal算法，构建出来的图是这样的：
   胖迪和海皇的关系被抹除了，其实我们之前的图里有环：
   

   Kruskal算法的时间复杂度主要取决于排序边的操作和并查集的效率。