c语言算法 – 贪婪算法 – 最小淹灭生成树
副标题#e#
在例1-2及1-3中已考查过这个问题。因为具有n 个极点的无向网络G的每个生成树恰好具有n-1条边，所以问题是用某种要领选择n-1条边使它们形成G的最小生成树。至少可以回收三种差异的贪婪计策来选择这n-1条边。这三种求解最小生成树的贪婪算法计策是： K r u s k a l算法，P r i m算法和S o l l i n算法。
1.Kruskal算法
(1) 算法思想
K r u s k a l算法每次选择n- 1条边，所利用的贪婪准则是：从剩下的边中选择一条不会发生环路的具有最小淹灭的边插手已选择的边的荟萃中。留意到所选取的边若发生环路则不行能形成一棵生成树。K r u s k a l算法分e 步，个中e 是网络中边的数目。按淹灭递增的顺序来思量这e 条边，每次思量一条边。当思量某条边时，若将其插手到已选边的荟萃中会呈现环路，则将其丢弃，不然，将它选入。
考查图1-12a 中的网络。初始时没有任何边被选择。图13-12b 显示了各节点的当前状态。边（ 1,6）是最先选入的边，它被插手到欲构建的生成树中，获得图1 3-1 2 c。下一步选择边（ 3，4）并将其插手树中（如图1 3-1 2 d所示）。然后思量边( 2，7)，将它插手树中并不会发生环路，于是便获得图1 3-1 2 e。下一步思量边（ 2，3）并将其插手树中（如图1 3-1 2 f所示）。在其余还未思量的边中，（7，4）具有最小淹灭，因此先思量它，将它插手正在建设的树中会发生环路，所以将其扬弃。从此将边（ 5，4）插手树中，获得的树如图13-12g 所示。下一步思量边（ 7，5），由于会发生环路，将其扬弃。最后思量边（ 6，5）并将其插手树中，发生了一棵生成树，其淹灭为9 9。图1-1 3给出了K r u s k a l算法的伪代码。
/ /在一个具有n 个极点的网络中找到一棵最小生成树
令T为所选边的荟萃，初始化T=
令E 为网络中边的荟萃
w h i l e(E≠)&&(| T |≠n- 1) {
令(u,v)为E中价钱最小的边 E=E- {(u,v)} / /从E中删除边
i f( (u,v)插手T中不会发生环路)将（ u,v）插手T
}
i f(| T |==n-1) T是最小淹灭生成树
e l s e 网络不是互连的，不能找到生成树
图13-13 Kruskao算法的伪代码
#p#副标题#e#
(2) 正确性证明
操作前述装载问题所用的转化技能可以证明图1 3-1 3的贪婪算法总能成立一棵最小淹灭生成树。需要证明以下两点： 1) 只要存在生成树，K r u s k a l算法总能发生一棵生成树； 2) 发生的生成树具有最小淹灭。令G为任意加权无向图（即G是一个无向网络）。从1 2 .11 .3节可知当且仅当一个无向图连通时它有生成树。并且在Kruskal 算法中被拒绝（扬弃）的边是那些会发生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此假如G在开始时是连通的，则T与E中的边总能形成一个连通图。也就是若G开始时是连通的，算法不会终止于E= 和| T |< n- 1。
此刻来证明所成立的生成树T具有最小淹灭。由于G具有有限棵生成树，所以它至少具有一棵最小生成树。令U为这样的一棵最小生成树， T与U都恰好有n- 1条边。假如T=U, 则T就具有最小淹灭，那么不必再证明下去。因此假设T≠U，令k(k >0) 为在T中而不在U中的边的个数，虽然k 也是在U中而不在T中的边的数目。 通过把U调动为T来证明U与T具有沟通的淹灭，这种转化可在k 步内完成。每一步使在T而不在U中的边的数目恰好减1。并且U的淹灭不会因为转化而改变。颠末k 步的转化获得的U将与本来的U具有沟通的淹灭，且转化后U中的边就是T中的边。由此可知， T具有最小淹灭。每步转化包罗从T中移一条边e 到U中，并从U中移出一条边f。边e 与f 的选取按如下方法举办：
1) 令e 是在T中而不在U中的具有最小淹灭的边。由于k >0，这条边必定存在。
2) 当把e插手U时，则会形成独一的一条环路。令f 为这条环路上不在T中的任意一条边。
由于T中不含环路，因此所形成的环路中至少有一条边不在T中。
从e 与f 的选择要领中可以看出， V=U+ {e}-{f} 是一棵生成树，且T中恰有k- 1条边不在V中呈现。此刻来证明V的淹灭与U的沟通。显然，V的淹灭便是U的淹灭加上边e 的淹灭再减去边f 的淹灭。若e 的淹灭比f 的小，则生成树V的淹灭比U的淹灭小，这是不行能的。假如e 的淹灭高于f，在K r u s k a l算法中f 会在e 之前被思量。由于f 不在T中，Kruskal 算法在思量f 可否插手T时已将f 扬弃，因此f 和T中淹灭小于或便是f 的边配合形成环路。通过选择e，所有这些边均在U中，因此U必定含有环路，可是实际上这不行能，因为U是一棵生成树。e 的价钱高于f 的假设将会导致抵牾。剩下的独一的大概是e 与f 具有沟通的淹灭，由此可知V与U的淹灭沟通。
(3) 数据布局的选择及巨大性阐明
#p#分页标题#e#
为了按淹灭非递减的顺序选择边，可以成立最小堆并按照需要从堆中一条一条地取出各边。当图中有e 条边时，需花(e) 的时间初始化堆及O ( l o ge) 的时间来选取每一条边。边的荟萃T与G中的极点一起界说了一个由至多n 个连通子图组成的图。用极点荟萃来描写每个子图，这些极点荟萃没有民众极点。为了确定边（ u,v）是否会发生环路，仅需查抄u,v 是否在同一个极点会合（即处于同一子图）。假如是，则会形成一个环路；假如不是，则不会发生环路。因此对付极点集利用两个F i n d操纵就足够了。当一条边包括在T中时，2个子图将被归并成一个子图，即对两个荟萃执行U n i o n操纵。荟萃的F i n d和U n i o n操纵可操作8 .1 0 .2节的树（以及加权法则和路径压缩）来高效地执行。F i n d操纵的次数最多为2e，Un i o n操纵的次数最多为n- 1（若网络是连通的，则恰好是n- 1次）。加上树的初始化时间，算法中这部门的巨大性只比O (n+e) 稍大一点。
对荟萃T所执行的独一操纵是向T中添加一条新边。T可用数组t 来实现。添加操纵在数组
的一端举办，因为最多可在T中插手n- 1条边，因此对T的操纵总时间为O (n)。
总结上述各个部门的执行时间，可得图1 3-1 3算法的渐进巨大性为O (n+el o ge)。
(4) 实现
操作上述数据布局，图1-1 3可用C + +代码来实现。首先界说E d g e N o d e类（见措施1 3-6)，它是最小堆的元素及生成树数组t 的数据范例。
措施13-6 Kruskal算法所需要的数据范例
template
class EdgeNode {
p u b l i c :
operator T() const {return weight;}
p r i v a t e :
T weight;//边的高度
int u, v;//边的端点
} ;
为了更简朴地利用8 .1 0 .2节的查找和归并计策，界说了U n i o n F i n d类，它的结构函数是措施8-1 6的初始化函数，U n i o n是措施8-1 6的加权归并函数，F i n d是措施8-1 7的路径压缩搜索函数。
为了编写与网络描写无关的代码，还界说了一个新的类U N e t Wo r k，它包括了应用于无向网络的所有函数。这个类与U n d i r e c t e d类的不同在于U n d i r e c t e d类中的函数不要求加权边，而U N e t Wo r k要求边必需带有权值。U N e t Wo r k中的成员需要操作N e t w o r k类中界说的诸如B e g i n和N e x t Ve r t e x的遍历函数。不外，新的遍历函数不只需要返回下一个连接的极点，并且要返回达到这个极点的边的权值。这些遍历函数以及有向和无向加权网络的其他函数一起组成了W N e t w o r k类（见措施1 3-7）。
措施13-7 WNetwork类
template
class WNetwork : virtual public Network
{
public :
virtual void First(int i, int& j, T& c)=0;
virtual void Next(int i, int& j, T& c)=0;
} ;
象B e g i n和N e x t Ve r t e x一样，可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类中插手函数F i r s t与N e x t。此刻A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类都需要从W N e t Wo r k中派生而来。由于A d j a c e n c y W G r a p h类和L i n k e d W G r a p h类需要会见U N e t w o r k的成员，所以这两个类还必需从U N e t Wo r k中派生而来。U N e t Wo r k : : K r u s k a l的代码见措施1 3-8，它要求将Edges() 界说为N e t Work 类的虚成员，而且把U N e t Wo r k界说为E d g e N o d e的友元）。假如没有生成树，函数返回f a l s e，不然返回t r u e。留意当返回true 时，在数组t 中返回最小淹灭生成树。
措施13-8 Kr u s k a l算法的C + +代码
template
bool UNetwork::Kruskal(EdgeNode t[])
{// 利用K r u s k a l算法寻找最小淹灭生成树
// 假如不连通则返回false
// 假如连通，则在t [ 0 : n-2 ]中返回最小生成树
int n=Ve r t i c e s () ;
int e=Edges();
/ /配置网络边的数组
InitializePos(); // 图遍历器
EdgeNode *E=new EdgeNode [e+1];
int k=0; // E的游标
for (int i=1; i <= n; i++) {// 使所有边隶属于i
int j;
T c;
First(i, j, c);
while (j) {// j 连接自i
if (i < j) {// 添加达到E的边
E[++k].weight=c;
E[k].u=i;
E[k].v=j;}
Next(i, j, c);
}
}
// 把边放入最小堆
MinHeap > H(1);
H.Initialize(E, e, e);
UnionFind U(n); // 归并/搜索布局
// 按照淹灭的序次来抽取边
k=0; // 此时作为t的游标
while (e && k < n-1) {
// 生成树未完成，另有剩余边
EdgeNode x;
H.DeleteMin(x); // 最小淹灭边
e-- ;
int a=U.Find(x.u);
int b=U.Find(x.v);
if (a != b) {// 选择边
t[k++]=x;
U .U n i o n ( a,b) ;}
}
D e a c t i v a t e P o s () ;
H .D e a c t i v a t e () ;
return (k== n-1);
}
2.Prim算法
#p#分页标题#e#
与Kr u s k a l算法雷同，P r i m算法通过每次选择多条边来建设最小生成树。选择下一条边的贪婪准则是：从剩余的边中，选择一条淹灭最小的边，而且它的插手应使所有入选的边仍是一棵树。最终，在所有步调中选择的边形成一棵树。相反，在Kruskal 算法中所有入选的边荟萃最终形成一个丛林。
P r i m算法从具有一个单一极点的树T开始，这个极点可以是原图中任意一个极点。然后往T中插手一条价钱最小的边（ u,v）使Tè{(u,v)}仍是一棵树，这种加边的步调重复轮回直到T中包括n- 1条边。留意对付边（ u,v），u、v 中正好有一个极点位于T中。P r i m算法的伪代码如图1 -1 4所示。在伪代码中也包括了所输入的图不是连通图的大概，在这种环境下没有生成树。图1-1 5显示了对图1-12a 利用P r i m算法的进程。把图1-1 4的伪代码细化为C + +措施及其正确性的证明留作操练（操练3 1）。
/ /假设网络中至少具有一个极点
设T为所选择的边的荟萃，初始化T=
设T V为已在树中的极点的荟萃，置T V= {1}
令E为网络中边的荟萃
w h i l e(E< >) & & (| T | < > n-1) {
令（u,v）为最小价钱边，个中u T V, v T V
i f（没有这种边） b re a k
E=E- {(u,v)} / /从E中删除此边
在T中插手边（ u,v）
}
if (| T |==n- 1) T是一棵最小生成树
else 网络是不连通的，没有最小生成树
图13-14 Prim最小生成树算法
假如按照每个不在T V中的极点v 选择一个极点n e ar (v)，使得n e ar (v) ? TV 且c o st (v, n e ar (v))的值是所有这样的n e ar (v) 节点中最小的，则实现P r i m算法的时间巨大性为O (n2)。下一条添加到T中的边是这样的边：其cost (v, near (v)) 最小，且v T V。
3.Sollin算法
S o l l i n算法每步选择若干条边。在每步开始时，所选择的边及图中的n个极点形成一个生成树的丛林。在每一步中为丛林中的每棵树选择一条边，这条边恰好有一个极点在树中且边的价钱最小。将所选择的边插手要建设的生成树中。留意一个丛林中的两棵树可选择同一条边，因此必需多次复制同一条边。当有多条边具有沟通的淹灭时，两棵树可选择与它们相连的差异的边，在这种环境下，必需扬弃个中的一条边。开始时，所选择的边的荟萃为空。若某一步竣事时仅剩下一棵树或没有剩余的边可供选择时算法终止。
图1-6给出了初始状态为图1-12a 时，利用S o l l i n算法的步调。初始入选边数为0时的景象如图13-12a 时,丛林中的每棵树均是单个极点。极点1，2，.，7所选择的边别离是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，个中差异的边是( 1,6)，( 2,7)，(3,4) 和( 5,4)，将这些边插手入选边的荟萃后所获得的功效如图1 3-1 6 a所示。下一步具有极点集{1,6}的树选择边( 6,5)，剩下的两棵树选择边( 2,3)，插手这两条边后已形成一棵生成树，构建好的生成树见图1 3-6 b。S o l l i n算法的C + +措施实现及其正确性证明留作操练（操练3 2)。
