图：最小生成树

文章目录

图：最小生成树简述Kruskal 算法基本过程伪码描述代码实现复杂度分析 Prim 算法基本过程伪码描述代码实现复杂度分析 引用

简述

按照不同的遍历算法，将得到不同的生成树；从不同的顶点出发，得到的生成树夜有所不同。对于一个带权图而言，不同的生成树对应的总权值夜不尽相同。所以，如何找到权值最小的生成树呢？ 典型的方法有两种：Kruskal算法和Prim算法

Kruskal 算法

基本过程

任意给定一个有n个节点的连通网络 N={ V , E }，首先构造一个由这n个顶点组成的、不含任何边的图 T = { V, ∅ } ，其中每个顶点自成一个连通分量。不断从E中取出权值最细小的一条边（若有多条，任取其一），若改变的两个端点来自不同的连通分量，则将刺鳊加入到T中。如此重复，知道所有顶点在同一连通分量上为止。 利用最小堆和并查集来实现Kruskal算法。首先利用最小堆来存放E中所有的边。堆中每个节点的格式为: tail（边的顶点位置）；head（边的顶点位置）;cost（边的权值） 在构造最小生成树的过程中，尚未处理的边存放在最小堆中。通过并查集的Find运算，可以很快地判断热议一条边的两个端点是否来自同一个连通分量。若是，则舍弃这条边；否则，将此边加入到T中，并通过并查集的Union运算，将两个端点各自所处的两个连通分量合二为一。随着T中边的不断增多，连通分量的逐步合并明知道最后主题构成一个连通分量为止。

伪码描述

T = ∅; while(T包含的变少于n-1&&E不空) { 从E中选一条具有最小代价（cost）的边（v ,w）; 从E中能够删去（v,w）; 如果（v,w）加到T中不会产生回路，则将（v,w）加入T; 否则放弃（v,w）; } if(T中包含的边数少于n-1条)则不是最小生成树;

代码实现

先给出最小生成树的类定义

const float maxValue=FLOAT_MAX; //机器可表示的、问题中不可能出现的大数 template<class T,class E> struct MSTEdgeNode //最小生成树边节点的类声明 { int tail,head;E key; //端点的位置和边的权值 MSTEdgeNode() :tail(-1),head(-1),key(0){}//构造函数 //操作符，自行补充 bool operator <= (MSTEdgeNode<T,E>&R){return key<=R.key; }; template<class T,class E> class MinSpanTree //最小生成树的类定义 { protected: MSTEdgeNode<T,E> *edgevalue; //用边值数组表示树 int maxSize, n //数组的最大元素个数和当前元素个数 public: MibnSpanTree(int sz=DefaultSize-1):MaxSize(Sz),n(0) {edgevalue=new MSTEdgeNode<T,E>[sz];} int Insert(MSTEdgeNode& item); };

在求解最小生成树的时候，可以使用邻接矩阵存储图，也可以用邻接表存储。算法中使用图的抽象基类操作，无需考录图及其操作的具体实现。

#include"heap.h" #include"UFSets.h" template<class T,class E> void Kruskal(Graph<T,E>& G,MinSpanTree<T,E> & MST) { MSTEdgeNode<T,E> ed;int u,v,count; //边节点辅助单元 int n=G.NumberOfVertices()； //顶点数 int m=G.NumberOfEdges(); //边数 MinHeap<MSTEdgeNode<T,E>> H(m); //最小堆，关键码类型为E UFSets F(n); //并查集 for(u=0;u<n;u++) { for(v=u+1;v<n;v++) { ed.tail=u;ed.head=v; //插入堆 ed.key=G.getWeight(u,v); H.Insert(ed); } } count=1; //最小生成树加入边数计数 while(count<n) //反复执行，去n-1条边 { //从最小堆中退出具有最小权值的边ed H.RemoveMib(ed); u=F.Find(ed.tail); //取两顶点所在集合的根u和v v=F.Find(ed.head); if(u!=v) //不是同一个集合，说明不连通 { F.Union(u,v); //合并，连通 MST.Insert(ed); //该边存入最小生成树 count++; } } }

复杂度分析

如果基于邻接矩阵实现图的存储，则建立在最小堆是需要检测图的邻接矩阵，这需要O(n²)的时间，此外，需要将e条边组成初始的最小堆。如果从空堆开始，依次插入各边，需要O(e$lo{g}_{2}e$)时间。在构造最小生成树的过程中，需要进行O(e)次出堆的操作RemoveMin( )、2次并查集的Find( )操作以及n-1次Union( )操作。所以计算的总时间为O(e$lo{g}_{2}e$+e$lo{g}_{2}n$+n²+n)。对连通图而言就是O(n²+e$lo{g}_{2}e$) 如果采用邻接表实现图的存储，则在建立最小堆的时候需要检测图的邻接表，需要O(n+e)的时间。为建成初始的最小堆。需要O(e$lo{g}_{2}e$)时间。在构造对象生成树的过程中，需要进行O(e)次出堆操作RemoveMin( )、2e次并查集的Find( )操作和n-1次Union( )操作，计算总时间为O(e$lo{g}_{2}e$+$lo{g}_{2}e$+n²+n)。对连通图而言就是O(n+e$lo{g}_{2}e$)。

Prim 算法

基本过程

与Kruskal算法类似，需要一个最小堆存储图的边，每次选出的一个端点在生成树中，另外一个端点不在生成树的权值最小的边，它正好在最小堆的顶端，将其从堆中退出，加入到生成树中。然后将新出现的所有端点在生成树中，一个端点不在生成树的边都插入最小堆中。下一次更迭中，下一条满足要求的权值最小的又上升到最小堆的顶端。如此重复n-1次。最有建立起最小生成树。

伪码描述

//选定构造最小生成树的顶点u V={u},E=∅//E是最小生成树的边集合，V是其顶点集合 while(V包含的顶点少于n&&E不空){ 从E中选择一条边(u,v),u∈V ∩ u∈!V，且具有最小代价; 令V=V∪(v),E=E∪{(u,v)}; 将新选出的边从E中剔除E=E-{(u,v)}; } if(V包含的顶点少于n)cout<<"不是最小生成树"<<endl;

代码实现

#include"heap.h" template<class T,class E> void Prim(Graph<T,E>& G,const T u0,MinSpan<T,E> &MST) { MSTEdgeNode<T,E>ed;int i,u,v,count;//边节点辅助单元 int n=G.NumberOfVertices();//顶点数 int m=G.NumberOfEdges();//边曙 int u=G.getVertexPos(u0);//求起始顶点号 MinHeap<MSTEdgeNode<T,E>>H(m);//最小堆，关键码为E bool Vmst=new bool[n];//最小生成树顶点集合 for(i=0;i<n;i++)Vmst[i]=false; Vmst[u]=true;//u加入生成树 count=1; do{ v=G.getFirstNeighbor(u);//迭代 while(v!=-1){//重复检测u的所有邻接点 if(Vmst[v]==false){//若v不在生成树，(u,v)加入堆 ed.tail=u;ed.head=v; ed.key=G.getWeight(u,v);//tail在树内，head不在树内 H.insert(ed); } v=G.getNextNeightbor(u,v); } while(!H.isEmpty()&&count<n) { H.RemoveMin(ed); if(Vmst[ed.head]==false){ MST.insert(ed); u=ed.head;Vmstu[u]=true; count++;break; } }while(count<n); }

复杂度分析

此算法的迭代次数为O(n)，每次迭代将平均2e/n条边插入最小堆中，e条边从典狱长删除，堆得插入和删除时间复杂性均为O($lo{g}_{2}e$)，则总的计算时间为O(e$lo{g}_{2}e$)。

引用

[1]殷人昆.《数据结构（用面向对象方法与c++语言描述）》.北京：清华大学，2007.6：371~375页.