c语言算法 - 贪婪算法 - 二分覆盖

核心提示：4.Undirected::BipartiteCover的实现函数的输入参数L用于分配图中的顶点（分配到集合A或B），L [i ]=1表示顶点i在集合A中，c语言算法 - 贪婪算法 - 二分覆盖(5)，L[ i ]=2则表示顶点在B中，函数有两个输出参数： C和m，然而A中的顶点由于New 值被更新，处于错误的双向链表

4.Undirected::BipartiteCover的实现

函数的输入参数L用于分配图中的顶点（分配到集合A或B）。L [i ]=1表示顶点i在集合A中，L[ i ]=2则表示顶点在B中。函数有两个输出参数： C和m，m为所建立的覆盖的大小，C [ 0 , m - 1 ]是A中形成覆盖的顶点。若二分图没有覆盖，函数返回f a l s e；否则返回t r u e。完整的代码见程序1 3 - 4。

程序13-4 构造贪婪覆盖

bool Undirected::BipartiteCover(int L[], int C[], int& m)
{// 寻找一个二分图覆盖
// L 是输入顶点的标号, L[i]=1 当且仅当i 在Ａ中
// C 是一个记录覆盖的输出数组
// 如果图中不存在覆盖，则返回f a l s e
// 如果图中有一个覆盖，则返回t r u e ;
// 在m中返回覆盖的大小; 在C [ 0 : m - 1 ]中返回覆盖
int n=Ve r t i c e s ( ) ;
// 插件结构
int SizeOfA=0;
for (int i=1; i <=n; i++) // 确定集合A的大小
if (L[i]==1) SizeOfA++;
int SizeOfB=n - SizeOfA;
CreateBins(SizeOfB, n);
int *New=new int [n+1]; / /顶点i覆盖了Ｂ中N e w [ i ]个未被覆盖的顶点
bool *Change=new bool [n+1]; // Change[i]为t r u e当且仅当New[i] 已改变
bool *Cov=new bool [n+1]; // Cov[i] 为true 当且仅当顶点i 被覆盖
I n i t i a l i z e P o s ( ) ;
LinkedStack S;
// 初始化
for (i=1; i <=n; i++) {
Cov[i]=Change[i]=false;
if (L[i]==1) {// i 在A中
New[i]=Degree(i); // i 覆盖了这么多
InsertBins(New[i], i);}}
// 构造覆盖
int covered=0, // 被覆盖的顶点
MaxBin=SizeOfB; // 可能非空的最大箱子
m=0; // C的游标
while (MaxBin > 0) { // 搜索所有箱子
// 选择一个顶点
if (bin[MaxBin]) { // 箱子不空
int v=bin[MaxBin]; // 第一个顶点
C[m++]=v; // 把v 加入覆盖
// 标记新覆盖的顶点
int j=Begin(v), k;
while (j) {
if (!Cov[j]) {// j尚未被覆盖
Cov[j]=true;
c o v e r e d + + ;
// 修改N e w
k=Begin(j);
while (k) {
New[k]--; // j 不计入在内
if (!Change[k]) {
S.Add(k); // 仅入栈一次
Change[k]=true;}
k=NextVe r t e x ( j ) ; }
}
j=NextVe r t e x ( v ) ; }
// 更新箱子
while (!S.IsEmpty()) {
S .D e l e t e ( k ) ;
Change[k]=false;
MoveBins(SizeOfB, New[k], k);}
}
else MaxBin--;
}
D e a c t i v a t e P o s ( ) ;
D e s t r o y B i n s ( ) ;
delete [] New;
delete [] Change;
delete [] Cov;
return (covered==SizeOfB);
}

程序1 3 - 4首先计算出集合A和B的大小、初始化必要的双向链表结构、创建三个数组、初始化图遍历器、并创建一个栈。然后将数组C o v和C h a n g e初始化为f a l s e，并将A中的顶点根据它们覆盖B中顶点的数目插入到相应的双向链表中。

为了构造覆盖，首先按SizeOfB 递减至1的顺序检查双向链表。当发现一个非空的表时，就将其第一个顶点v 加入到覆盖中，这种策略即为选择具有最大Ne o v [ j ]置为t r u e，表示顶点j 现在已被覆盖，同时将已被覆盖的B中的顶点数目加1。由于j 是最近被覆w 值的顶点。将所选择的顶点加入覆盖数组C并检查B中所有与它邻接的顶点。若顶点j 与v 邻接且还未被覆盖，则将C盖的，所有A中与j 邻接的顶点的New 值减1。下一个while 循环降低这些New 值并将New 值被降低的顶点保存在一个栈中。当所有与顶点v邻接的顶点的Cov 值更新完毕后，N e w值反映了A中每个顶点所能覆盖的新的顶点数，然而A中的顶点由于New 值被更新，处于错误的双向链表中，下一个while 循环则将这些顶点移到正确的表中。