二分图是一个无向图,它的n 个顶点可二分为集合A和集合B,且同一集合中的任意两个顶点在图中无边相连(即任何一条边都是一个顶点在集合A中,另一个在集合B中)。当且仅当B中的每个顶点至少与A中一个顶点相连时,A的一个子集A' 覆盖集合B(或简单地说,A' 是一个覆盖)。覆盖A' 的大小即为A' 中的顶点数目。当且仅当A' 是覆盖B的子集中最小的时,A' 为最小覆盖。
例1-10 考察如图1 - 6所示的具有1 7个顶点的二分图,A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15},子集A' = { 1 , 1 6 , 1 7 }是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖( b i p a r t i t e - c o v e r)问题。在例1 2 - 3中说明了最小覆盖是很有用的,因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。
二分覆盖问题类似于集合覆盖( s e t - c o v e r)问题。在集合覆盖问题中给出了k 个集合S= {S1 , S2 ,., Sk },每个集合Si 中的元素均是全集U中的成员。当且仅当èi S'Si =U时,S的子集S' 覆盖U,S '中的集合数目即为覆盖的大小。当且仅当没有能覆盖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私有成员
程序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不为0,则将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 ] = 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 在A中
// 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覆盖了B中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 循环则将这些顶点移到正确的表中。
转载自沙大工作室