0025算法笔记——【贪心算法】最小生成树问题

     设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

     网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 

     2、MST性质

     设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)ÎE，且uÎU，vÎV-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。 

     MST性质的证明：如图所示，假设G的任何一颗最小生成树都不包含边(u,v)。将边(u,v)添加到G的一颗最小生成树T上，将产生含有边(u,v)的圈，并且在这个圈上有一条不同于(u,v)的边(u’,v’)，使得u’ÎU，v‘ÎV-U。将边(u’,v’)删去，得到G的另一颗生成树T’。由于c[u][v]<=c[u’][v’]，所以T’的耗费<=T的耗费。于是T’是一颗含有边(u,v)的最小生成树，这与假设矛盾。

     3、Prim算法

     设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iÎS，jÎV-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 

     算法具体代码如下：

//4d6 贪心算法 最小生成树 Prim算法 #include "stdafx.h" #include <fstream> #include <string> #include <iostream> using namespace std; #define inf 9999; const int N = 6; ifstream fin("4d6.txt"); template<class Type> void Prim(int n,Type c[][N+1]); int main() { int c[N+1][N+1]; cout<<"连通带权图的矩阵为："<<endl; for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { fin>>c[i][j]; cout<<c[i][j]<<" "; } cout<<endl; } cout<<"Prim算法最小生成树选边次序如下："<<endl; Prim(N,c); return 0; } template<class Type> void Prim(int n,Type c[][N+1]) { Type lowcost[N+1];//记录c[j][closest]的最小权值 int closest[N+1];//V-S中点j在S中的最邻接顶点 bool s[N+1]; s[1] = true; //初始化s[i],lowcost[i],closest[i] for(int i=2; i<=n; i++) { lowcost[i] = c[1][i]; closest[i] = 1; s[i] = false; } for(int i=1; i<n; i++) { Type min = inf; int j = 1; for(int k=2; k<=n; k++)//找出V-S中使lowcost最小的顶点j { if((lowcost[k]<min)&&(!s[k])) { min = lowcost[k]; j = k; } } cout<<j<<' '<<closest[j]<<endl; s[j] = true;//将j添加到S中 for(int k=2; k<=n; k++)//将j添加到S中后，修改closest和lowcost的值 { if((c[j][k]<lowcost[k] && (!s[k]))) { lowcost[k] = c[j][k]; closest[k] = j; } } } }

        
上述代码中，数组closest[j]是j(
j
Î
V-S)在S中的领接顶点，它与j在S中的其它顶点相比较有c[j][cloest[j]]<=c[j][k]。lowest[j]的值就是c[j][cloest[j]]。在算法执行过程中，先找出V-S中是lowest值最小的顶点j，然后根据数组closest选取边(j,cloest[j])，最后将j添加到S中，并对closest和lowest作必要的修改。

     程序运行结果为：

      例如，对于下图中的带权图，按Prim算法选取边的过程如图所示：

     利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树，Prim算法所需要的计算时间为O(n^2)。

     4、Kruskal算法

     Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

     实现算法Kruskal需要准备两个数据结构：(1)最小堆MinHeap，按权的递增顺序查看的边的序列可以看做是一个优先队列，它的优先级为边权；(2)并查集UnionFind，主要包括Union(a,b)和Find(v)两个基本运算：Union(a,b)将两个连通分支a和b连接起来，所得的结果为A或B；Find(v)返货U总包含顶点v的连通分支的名字。这个运算用来确定某条边的两个端点所属的连通分支。

    具体代码如下：

     (1)MinHeap.h

#include <iostream> using namespace std; template<class T> class MinHeap { private: T *heap; //元素数组，0号位置也储存元素 int CurrentSize; //目前元素个数 int MaxSize; //可容纳的最多元素个数 void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上 void FilterUp(int start); //自下往上调整 public: MinHeap(int n=1000); ~MinHeap(); bool Insert(const T &x); //插入元素 T RemoveMin(); //删除最小元素 T GetMin(); //取最小元素 bool IsEmpty() const; bool IsFull() const; void Clear(); }; template<class T> MinHeap<T>::MinHeap(int n) { MaxSize=n; heap=new T[MaxSize]; CurrentSize=0; } template<class T> MinHeap<T>::~MinHeap() { delete []heap; } template<class T> void MinHeap<T>::FilterUp(int start) //自下往上调整 { int j=start,i=(j-1)/2; //i指向j的双亲节点 T temp=heap[j]; while(j>0) { if(heap[i]<=temp) break; else { heap[j]=heap[i]; j=i; i=(i-1)/2; } } heap[j]=temp; } template<class T> void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上 { int i=start,j=2*i+1; T temp=heap[i]; while(j<=end) { if( (j<end) && (heap[j]>heap[j+1]) ) j++; if(temp<=heap[j]) break; else { heap[i]=heap[j]; i=j; j=2*j+1; } } heap[i]=temp; } template<class T> bool MinHeap<T>::Insert(const T &x) { if(CurrentSize==MaxSize) return false; heap[CurrentSize]=x; FilterUp(CurrentSize); CurrentSize++; return true; } template<class T> T MinHeap<T>::RemoveMin( ) { T x=heap[0]; heap[0]=heap[CurrentSize-1]; CurrentSize--; FilterDown(0,CurrentSize-1); //调整新的根节点 return x; } template<class T> T MinHeap<T>::GetMin() { return heap[0]; } template<class T> bool MinHeap<T>::IsEmpty() const { return CurrentSize==0; } template<class T> bool MinHeap<T>::IsFull() const { return CurrentSize==MaxSize; } template<class T> void MinHeap<T>::Clear() { CurrentSize=0; }

     (2)UnionFind.h

class UnionFind { public: UnionFind(int); ~UnionFind(); public: int Find(int); void Union(int, int); private: int EleNum; int *Parents; int *Rank; }; UnionFind::UnionFind(int n) { EleNum = n; Parents = new int[EleNum]; Rank = new int[EleNum]; for(int i = 0; i < EleNum; i++) { Parents[i] = -1; Rank[i] = 1; } } UnionFind::~UnionFind() { delete[] Parents; delete[] Rank; } int UnionFind::Find(int i) { int r = i; while(Parents[r] != -1) r = Parents[r]; while(r != i) { int q = Parents[i]; Parents[i] = r; i = q; } return r; } void UnionFind::Union(int i, int j) { int a = Find(i); int b = Find(j); if(a == b) return; if(Rank[a] > Rank[b]) { Parents[b] = a; Rank[a] += Rank[b]; } else { Parents[a] = b; Rank[b] += Rank[a]; } }

     (3)4d6-2.cpp

//4d6-2 贪心算法 最小生成树 Kruskal算法 #include "stdafx.h" #include "MinHeap.h" #include "UnionFind.h" #include <fstream> #include <string> #include <iostream> using namespace std; const int N = 10;//图的边数 const int M = 6;//图的顶点数 ifstream fin("4d6-2.txt"); template <class Type> class EdgeNode { friend ostream& operator <<(ostream&,EdgeNode<Type>); //不知道为什么，一去掉注释就会报错误LNK2019: 无法解析的外部符号 错误 //friend bool Kruskal(int,int,EdgeNode<Type>[],EdgeNode<Type>[]); friend int main(void); public: operator Type() const { return weight; } //暂时这么放了，日后解决 //private: Type weight; int u,v; }; template <class Type> bool Kruskal(int n,int e,EdgeNode<Type> E[],EdgeNode<Type> t[]); int main() { EdgeNode<int> E[N+1],t[N+1];//存储连通带权图所有边的两端顶点，权) cout<<"连通带权图所有边的两端顶点，权分别为："<<endl; for(int i=1; i<=N; i++) { fin>>E[i].u>>E[i].weight>>E[i].v; cout<<"u:"<<E[i].u<<",weight:"<<E[i].weight<<",v:"<<E[i].v; cout<<endl; } if(Kruskal(M+1,N,E,t)) { cout<<"Kruskal算法最小生成树选择结果为:"<<endl; for(int i=1; i<M; i++) { cout<<"u:"<<t[i].u<<",weight:"<<t[i].weight<<",v:"<<t[i].v; cout<<endl; } } return 0; } template <class Type> bool Kruskal(int n,int e,EdgeNode<Type> E[],EdgeNode<Type> t[]) { MinHeap<EdgeNode<Type>> H(e); //初始化最小堆 for(int i=1; i<=e; i++) H.Insert(E[i]); UnionFind U(n); int k = 1; while(e && k<n-1) { EdgeNode<int> x; x = H.RemoveMin(); e--; //返回u中包含顶点V的连通分支的名字 int a = U.Find(x.u); int b = U.Find(x.v); if(a!=b) { t[k++] = x; U.Union(a,b); } } return (k==n-1); }

     
例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示：

     当图的边数为e时，Kruskal算法所需的计算时间是 。当时，Kruskal算法比Prim算法差，但当时，Kruskal算法却比Prim算法好得多。程序运行结果为：