二分图是一个无向图它的n 个顶点可二分为集合A和集合B且同一集合中的任意两个顶点在图中无边相连(即任何一条边都是一个顶点在集合A中另一个在集合B中)当且仅当B中的每个顶点至少与A中一个顶点相连时A的一个子集A 覆盖集合B(或简单地说A 是一个覆盖)覆盖A 的大小即为A 中的顶点数目当且仅当A 是覆盖B的子集中最小的时A 为最小覆盖
例 考察如图 所示的具有 个顶点的二分图A={ }和B={ }子集A = { }是B的最小覆盖在二分图中寻找最小覆盖的问题为二分覆盖( b i p a r t i t e c o v e r)问题在例 中说明了最小覆盖是很有用的因为它能解决在会议中使用最少的翻译人员进行翻译这一类的问题
二分覆盖问题类似于集合覆盖( s e t c o v e r)问题在集合覆盖问题中给出了k 个集合S= {S S Sk }每个集合Si 中的元素均是全集U中的成员当且仅当èi SSi =U时S的子集S 覆盖US 中的集合数目即为覆盖的大小当且仅当没有能覆盖U的更小的集合时称S 为最小覆盖可以将集合覆盖问题转化为二分覆盖问题(反之亦然)即用A的顶点来表示S Sk B中的顶点代表U中的元素当且仅当S的相应集合中包含U中的对应元素时在A与B的顶点之间存在一条边
例 令S= {S S } U= { } S = { }S = { }S = { }S = { }S = { }S = {SSS }是一个大小为的覆盖没有更小的覆盖 S 即为最小覆盖这个集合覆盖问题可映射为图的二分图即用顶点 和 分别表示集合SSSS 和S顶点j 表示集合中的元素j≤j≤
集合覆盖问题为N P复杂问题由于集合覆盖与二分覆盖是同一类问题二分覆盖问题也是N P复杂问题因此可能无法找到一个快速的算法来解决它但是可以利用贪婪算法寻找一种快速启发式方法一种可能是分步建立覆盖A 每一步选择A中的一个顶点加入覆盖顶点的选择利用贪婪准则从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点
例 考察图 所示的二分图初始化A = 且B中没有顶点被覆盖顶点和 均能覆盖B中的六个顶点顶点覆盖五个顶点和 分别覆盖四个因此在第一步往A 中加入顶点或 若加入顶点 则它覆盖的顶点为{ }未覆盖的顶点为{ }顶点能覆盖其中四个顶点( { })顶点 覆盖一个( { } )顶点覆盖一个({ })顶点 覆盖零个顶点 覆盖四个{ }下一步可选择或 加入A 若选择顶点则顶点{ } 仍然未被覆盖此时顶点 不覆盖其中任意一个顶点覆盖一个顶点 覆盖两个因此选择顶点 至此所有顶点已被覆盖得A = { }
图 给出了贪婪覆盖启发式方法的伪代码可以证明 ) 当且仅当初始的二分图没有覆盖时算法找不到覆盖;) 启发式方法可能找不到二分图的最小覆盖
数据结构的选取及复杂性分析
为实现图 的算法需要选择A 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目由于对集合A 仅使用加法运算则可用一维整型数组C来描述A 用m 来记录A 中元素个数将A 中的成员记录在C[ :m] 中对于A中顶点i令N e wi 为i 所能覆盖的B中未覆盖的顶点数目逐步选择N e wi 值最大的顶点由于一些原来未被覆盖的顶点现在被覆盖了因此还要修改各N e wi 值在这种更新中检查B中最近一次被V覆盖的顶点令j 为这样的一个顶点则A中所有覆盖j 的顶点的N e wi 值均减
例 考察图 初始时(N e w N e w N e w N e w N e w ) = ( )假设在例 中第一步选择顶点 为更新N e wi 的值检查B中所有最近被覆盖的顶点这些顶点为 和 当检查顶点时将顶点和 的N e wi 值分别减因为顶点不再是被顶点和 覆盖的未覆盖节点;当检查顶点时顶点 和 的相应值分别减;同样检查顶点时和 的值分别减;当检查完所有最近被覆盖的顶点得到的N e wi 值为()下一步选择顶点最新被覆盖的顶点为和 ;检查顶点时N e w N e w 和N e w 的值减;检查顶点时N e w 的值减因为顶点是覆盖的唯一顶点
为了实现顶点选取的过程需要知道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现将图 的伪代码进行细化得到图
m=; //当前覆盖的大小
对于A中的所有iNew[i]=Degree[i]
对于B中的所有iC o v [ i ] = f a l s e
while (对于A中的某些iNew[i]>) {
设v是具有最大的N e w [ i ]的顶点;
C [ m + + ] = v ;
for ( 所有邻接于v的顶点j) {
if (!Cov[j]) {
Cov[j]= true;
对于所有邻接于j的顶点使其N e w [ k ]减
} } }
if (有些顶点未被覆盖) 失败
else 找到一个覆盖
图 图的细化
更新N e w的时间为O (e)其中e 为二分图中边的数目若使用邻接矩阵则需花(n ) 的时间来寻找图中的边若用邻接链表则需(n+e) 的时间实际更新时间根据描述方法的不同为O (n ) 或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 +n) = O ( n)或O (S i z e Of A+n + e)
降低复杂性
通过使用有序数组N e wi最大堆或最大选择树(max selection tree)可将每步选取顶点v的复杂性降为( )但利用有序数组在每步的最后需对N e wi 值进行重新排序若使用箱子排序则这种排序所需时间为(S i z e O f B ) ( S i z e O fB =|B| ) (见 节箱子排序)由于一般S i z e O f B比S i z e O f A大得多因此有序数组并不总能提高性能
如果利用最大堆则每一步都需要重建堆来记录N e w值的变化可以在每次N e w值减时进行重建这种减法操作可引起被减的N e w值最多在堆中向下移一层因此这种重建对于每次N e w值减需( )的时间总共的减操作数目为O (e)因此在算法的所有步骤中维持最大堆仅需O (e)的时间因而利用最大堆时覆盖算法的总复杂性为O (n )或O (n+e)
若利用最大选择树每次更新N e w值时需要重建选择树所需时间为(log S i z e O f A)重建的最好时机是在每步结束时而不是在每次N e w值减时需要重建的次数为O (e)因此总的重建时间为O (e log S i z e OfA)这个时间比最大堆的重建时间长一些然而通过维持具有相同N e w值的顶点箱子也可获得和利用最大堆时相同的时间限制由于N e w的取值范围为到S i z e O f B需要S i z e O f B+ 个箱子箱子i 是一个双向链表链接所有N e w值为i 的顶点在某一步结束时假如N e w [ ]从 变到则需要将它从第 个箱子移到第个箱子利用模拟指针及一个节点数组n o d e(其中n o d e [ i ]代表顶点in o d e [ i ] l e f t和n o d e [ i ] r i g h t为双向链表指针)可将顶点从第 个箱子移到第个箱子从第 个箱子中删除n o d e [ ]并将其插入第个箱子利用这种箱子模式可得覆盖启发式算法的复杂性为O (n )或O(n+e)(取决于利用邻接矩阵还是线性表来描述图)
双向链接箱子的实现
为了实现上述双向链接箱子图 定义了类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的类它的数据类型是双向链表节点程序 给出了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的节点
图 实现双向链接箱子所需的U n d i r e c t e d私有成员
程序 箱子函数的定义
void Undirected::CreateBins(int b int n)
{// 创建b个空箱子和n个节点
node = new NodeType [n+];
bin = new int [b+];
// 将箱子置空
for (int i = ; i <= b; i++)
bin[i] = ;
}
void Undirected::InsertBins(int b int v)
{// 若b不为则将v 插入箱子b
if (!b) return; // b为不插入
node[v]left = b; // 添加在左端
if (bin) node[bin]left = v;
node[v]right = bin;
bin
