'中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S'
为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1 , ., Sk
，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。
例1 - 11 令S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1
3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1
4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4，S5 }是一个大小为3的覆盖，没有更小的覆盖，
S' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4
和S5，顶点j 表示集合中的元素j，4≤j≤1 5。 集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N
P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A'
，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。
例1-12 考察图1 - 6所示的二分图，初始化A' = 且B中没有顶点被覆盖，顶点1和1
6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A' 中加入顶点1或1 6，若加入顶点1
6，则它覆盖的顶点为{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆盖的顶点为{ 4 , 7 , 9 , 1 0
, 11 , 1 3 }。顶点1能覆盖其中四个顶点（ { 4 , 7 , 9 , 1 3 }），顶点2 覆盖一个( { 4 }
)，顶点3覆盖一个（{ 1 0 }），顶点1 6覆盖零个，顶点1 7覆盖四个{ 4 , 9 , 1 0 , 11
}。下一步可选择1或1 7加入A' 。若选择顶点1，则顶点{ 1 0 , 11} 仍然未被覆盖，此时顶点1，2，1
6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A' = { 1 6 , 1 , 1 7 }。
图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2)
启发式方法可能找不到二分图的最小覆盖。
1. 数据结构的选取及复杂性分析
为实现图13 - 7的算法，需要选择A' 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A'
仅使用加法运算，则可用一维整型数组C来描述A '，用m 来记录A' 中元素个数。将A' 中的成员记录在C[ 0 :m-1]
中。对于A中顶点i，令N e wi 为i 所能覆盖的B中未覆盖的顶点数目。逐步选择N e wi
值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各N e wi
值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，则A中所有覆盖j 的顶点的N e wi 值均减1。
例1-13 考察图1 - 6，初始时(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 )
= ( 6 , 4 , 5 , 6 , 4 )。假设在例1 - 1 2中，第一步选择顶点1 6，为更新N e wi
的值检查B中所有最近被覆盖的顶点，这些顶点为5 , 6 , 8 , 1 2 , 1 4和1 5。当检查顶点5时，将顶点2和1 6的N
e wi 值分别减1，因为顶点5不再是被顶点2和1 6覆盖的未覆盖节点；当检查顶点6时，顶点1 , 2 ,和1
6的相应值分别减1；同样，检查顶点8时，1，2，3和1 6的值分别减1；当检查完所有最近被覆盖的顶点，得到的N e wi
值为（4，1，0，4）。下一步选择顶点1，最新被覆盖的顶点为4，7，9和1 3；检查顶点4时，N e w1 , N e w2, 和N
e w1 7 的值减1；检查顶点7时，N e w1 的值减1，因为顶点1是覆盖7的唯一顶点。
为了实现顶点选取的过程，需要知道N e wi 的值及已被覆盖的顶点。可利用一个二维数组来达到这个目的，N e
w是一个整型数组，New[i] 即等于N e wi，且c o v为一个布尔数组。若顶点i未被覆盖则c o v [ i ]等于f a
l s e，否则c o v [ i ]为t r u e。现将图1 - 7的伪代码进行细化得到图1 - 8。
m=0; //当前覆盖的大小
对于A中的所有i，New[i]=Degree[i]
对于B中的所有i，C o v [ i ] = f a l s e while (对于A中的某些i,New[i]>0) { 设v是具有最大的N e w [ i ]的顶点； C [ m + + ] = v ;
for ( 所有邻接于v的顶点j) { if (!Cov[j]) {
Cov[j]= true;
对于所有邻接于j的顶点，使其N e w [ k ]减1 } } }
if (有些顶点未被覆盖) 失败 else 找到一个覆盖
图1-8 图1-7的细化 更新N e w的时间为O (e)，其中e 为二分图中边的数目。若使用邻接矩阵，则需花(n2 )
的时间来寻找图中的边，若用邻接链表，则需(n+e) 的时间。实际更新时间根据描述方法的不同为O (n2 ) 或O
(n+e)。逐步选择顶点所需时间为(S i z e O f A)，其中S i z e O f A=| A |。因为A的所有顶点都有可能被选择，因此所需步骤数为O ( S i z e O f A )，覆盖算法总的复杂性为O ( S i z
e O f A 2+n2) = O ( n2)或O (S i z e Of A2+n + e)。 2. 降低复杂性
通过使用有序数组N e wi、最大堆或最大选择树（max selection tree）可将每步选取顶点v的复杂性降为( 1
)。但利用有序数组，在每步的最后需对N e wi 值进行重新排序。若使用箱子排序，则这种排序所需时间为(S i z e O f B
) ( S i z e O fB =|B| ) （见3 . 8 . 1节箱子排序）。由于一般S i z e O f B比S i z
e O f A大得多，因此有序数组并不总能提高性能。
如果利用最大堆，则每一步都需要重建堆来记录N e w值的变化，可以在每次N e w值减1时进行重建。这种减法操作可引起被减的N e
w值最多在堆中向下移一层，因此这种重建对于每次N e w值减1需( 1 )的时间，总共的减操作数目为O
(e)。因此在算法的所有步骤中，维持最大堆仅需O (e)的时间，因而利用最大堆时覆盖算法的总复杂性为O (n2 )或O (n+e)。 若利用最大选择树，每次更新N e w值时需要重建选择树，所需时间为(log S i z e O f
A)。重建的最好时机是在每步结束时，而不是在每次N e w值减1时，需要重建的次数为O (e)，因此总的重建时间为O (e log
S i z e OfA)，这个时间比最大堆的重建时间长一些。然而，通过维持具有相同N e
w值的顶点箱子，也可获得和利用最大堆时相同的时间限制。由于N e w的取值范围为0到S i z e O f B，需要S i z e
O f B+ 1个箱子，箱子i 是一个双向链表，链接所有N e w值为i 的顶点。在某一步结束时，假如N e w [ 6 ]从1 2变到4，则需要将它从第1 2个箱子移到第4个箱子。利用模拟指针及一个节点数组n o d e（其中n o d e [ i
]代表顶点i，n o d e [ i ] . l e f t和n o d e [ i ] . r i g h t为双向链表指针），可将顶点6从第1 2个箱子移到第4个箱子，从第1 2个箱子中删除n o d e [ 0
]并将其插入第4个箱子。利用这种箱子模式，可得覆盖启发式算法的复杂性为O (n2
)或O(n+e)。（取决于利用邻接矩阵还是线性表来描述图）。 3. 双向链接箱子的实现
为了实现上述双向链接箱子，图1 - 9定义了类U n d i r e c t e d的私有成员。N o d e Ty p
e是一个具有私有整型成员l e f t和r i g h t的类，它的数据类型是双向链表节点，程序1 3 - 3给出了U n d i r e c t e d的私有成员的代码。 void CreateBins (int b, int n) 创建b个空箱子和n个节点
void DestroyBins() { delete [] node; delete [] bin;}
void InsertBins(int b, int v) 在箱子b中添加顶点v
void MoveBins(int bMax, int ToBin, int v) 从当前箱子中移动顶点v到箱子To B i n int *bin;
b i n [ i ]指向代表该箱子的双向链表的首节点 N o d e Type *node;
n o d e [ i ]代表存储顶点i的节点
图1-9 实现双向链接箱子所需的U n d i r e c t e d私有成员
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-27 19:40:45
b
等级：职业侠客 文章：470 积分：956
门派：黑客帝国 注册：2003-8-28
第 8 楼
程序13-3 箱子函数的定义
void Undirected::CreateBins(int b, int n) {// 创建b个空箱子和n个节点 node = new NodeType [n+1]; bin = new int [b+1]; // 将箱子置空
for (int i = 1; i <= b; i++) bin[i] = 0; }
void Undirected::InsertBins(int b, int v) {// 若b不为０，则将v 插入箱子b if (!b) return; // b为0，不插入 node[v].left = b; // 添加在左端 if (bin[b]) node[bin[b]].left = v; node[v].right = bin[b]; bin[b] = v;
}
void Undirected::MoveBins(int bMax, int ToBin, int v) {// 将顶点v 从其当前所在箱子移动到To B i n . // v的左、右节点 int l = node[v].left; int r = node[v].right; // 从当前箱子中删除
if (r) node[r].left = node[v].left;
if (l > bMax || bin[l] != v) // 不是最左节点 node[l].right = r;
else bin[l] = r; // 箱子l的最左边 // 添加到箱子To B i n
I n s e r t B i n s ( ToBin, v); }
函数C r e a t e B i n s动态分配两个数组： n o d e和b i n，n o d e [i ]表示顶点i,
bin[i ]指向其N e w值为i的双向链表的顶点, f o r循环将所有双向链表置为空。如果b≠0，函数InsertBins
将顶点v 插入箱子b 中。因为b 是顶点v 的New 值，b = 0意味着顶点v 不能覆盖B中当前还未被覆盖的任何顶点，所以，在建立覆盖时这个箱子没有用处，故可以将其舍去。当b≠0时，顶点n 加入New 值为b
的双向链表箱子的最前面，这种加入方式需要将node[v] 加入bin[b] 中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的node[v].left
置为b。若箱子不空，则当前第一个节点的left 指针被置为指向新节点。node[v] 的右指针被置为b i n [ b
]，其值可能为0或指向上一个首节点的指针。最后， b i n [ b ]被更新为指向表中新的第一个节点。MoveBins 将顶点v
从它在双向链表中的当前位置移到New 值为ToBin 的位置上。其中存在bMa x，使得对所有的箱子b i n[ j
]都有：如j>bMa x，则b i n [ j ]为空。代码首先确定n o d e [ v ]在当前双向链表中的左右节点，接着从双链表中取出n o d e [ v ]，并利用I n s e r t B i n
s函数将其重新插入到b i n [ To B i n ]中。
4. Undirected::BipartiteCover的实现
函数的输入参数L用于分配图中的顶点（分配到集合A或B）。L [i ] = 1表示顶点i在集合A中，L[ i ] =