二分覆盖

韩冰

<>二分图是一个无向图，它的n 个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A' 覆盖集合B（或简单地说，A' 是一个覆盖）。覆盖A' 的大小即为A' 中的顶点数目。当且仅当A' 是覆盖B的子集中最小的时，A' 为最小覆盖。</P>
<>例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中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。</P>
2 w1 S% z# w% h& I4 g  p<>二分覆盖问题类似于集合覆盖（ 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的顶点之间存在一条边。</P>
<>例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。</P>
( f0 k( Y( l9 c' d<>集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。</P>
7 f' Y# Y2 Y3 p. o4 S<>例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 }。</P>
<>图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。</P>
7 U+ f* @2 }5 m- G<>1. 数据结构的选取及复杂性分析</P>
<>为实现图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。</P>
- p, k+ b9 h: Q* G8 p' r<>例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的唯一顶点。</P>
+ n+ \% o, T. s0 h<>为了实现顶点选取的过程，需要知道N e wi 的值及已被覆盖的顶点。可利用一个二维数组来达到这个目的，N e w是一个整型数组，New 即等于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。</P>
<>m=0; //当前覆盖的大小</P>
0 T% c. F8 d9 A; _" _+ W+ H, F' o; B<>对于A中的所有i，New=Degree</P>
<>对于B中的所有i，C o v [ i ] = f a l s e</P>
& d/ Y+ r  G: z% e/ P8 I: |<>while (对于A中的某些i,New&gt;0) {</P>
<>设v是具有最大的N e w [ i ]的顶点；</P>
<>C [ m + + ] = v ;</P>
  g2 i; a1 x6 ~<>for ( 所有邻接于v的顶点j) {</P>
, ?5 e+ W% T( X/ [1 ^3 }, J<>if (!Cov[j]) {</P>
<>Cov[j]= true;</P>
<>对于所有邻接于j的顶点，使其N e w [ k ]减1</P>
( j- {' F9 l; }<>} } }</P>
<>if (有些顶点未被覆盖) 失败</P>
$ N, H+ a5 R" e<>else 找到一个覆盖</P>
<>图1-8 图1-7的细化</P>
9 O/ N3 ^; o- M- f<>更新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)。</P>
: s) W+ W, F7 z+ q# J1 ~* f<>2. 降低复杂性</P>
: V4 @1 g( ?  S( K: F<>通过使用有序数组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大得多，因此有序数组并不总能提高性能。</P>
2 ?" e' N: u) J% P<>如果利用最大堆，则每一步都需要重建堆来记录N e w值的变化，可以在每次N e w值减1时进行重建。这种减法操作可引起被减的N e w值最多在堆中向下移一层，因此这种重建对于每次N e w值减1需( 1 )的时间，总共的减操作数目为O (e)。因此在算法的所有步骤中，维持最大堆仅需O (e)的时间，因而利用最大堆时覆盖算法的总复杂性为O (n2 )或O (n+e)。</P>
<>若利用最大选择树，每次更新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)。（取决于利用邻接矩阵还是线性表来描述图）。</P>
3 l+ V- `3 R) J<P>3. 双向链接箱子的实现</P>
# ~$ l0 U5 ?0 [. t, n6 l<P>为了实现上述双向链接箱子，图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的私有成员的代码。</P>
& n7 S) n/ B; m/ d- h
3 k7 e& I9 G/ P9 N! Z; f
<P>void CreateBins (int b, int n)</P>
<P>创建b个空箱子和n个节点</P>
4 V& U0 `% T" G0 K5 i2 |<P>void DestroyBins() { delete [] node;</P>
<P>delete [] bin;}</P>
! F0 ]- c8 s4 R+ }8 l0 e<P>void InsertBins(int b, int v)</P>
+ q, L1 L) Z/ M9 M% z: j1 m- ^- S: y$ }/ f<P>在箱子b中添加顶点v</P>
8 B& D3 L6 k& {: X<P>void MoveBins(int bMax, int ToBin, int v)</P>
! S! j  u  @( ^9 M/ B: S8 a<P>从当前箱子中移动顶点v到箱子To B i n</P>
<P>int *bin;</P>
! K4 j% W. D- O$ U* Q7 r! v<P>b i n [ i ]指向代表该箱子的双向链表的首节点</P>
<P>N o d e Type *node;</P>
, t9 L! Y: u6 ]9 w$ ]<P>n o d e [ i ]代表存储顶点i的节点</P>
) k' [! H0 A; u; H8 M8 L5 _<P>图1-9 实现双向链接箱子所需的U n d i r e c t e d私有成员</P>
<p>
<P>程序13-3 箱子函数的定义</P>
<P>void Undirected::CreateBins(int b, int n)</P>
' N, ~- o; Q4 T. O( q- v<P>{// 创建b个空箱子和n个节点</P>
<P>node = new NodeType [n+1];</P>
<P>bin = new int [b+1];</P>
<P>// 将箱子置空</P>
0 l# _$ H  B4 p( y1 c<P>for (int i = 1; i &lt;= b; i++)</P>
<P>bin = 0;</P>
& n$ \* u5 Y9 d# a; _: I/ K7 P. ^<P>}</P>
<P>void Undirected::InsertBins(int b, int v)</P>
<P>{// 若b不为０，则将v 插入箱子b</P>
<P>if (!b) return; // b为0，不插入</P>
" Z2 L8 t6 e( \$ Z<P>node[v].left = b; // 添加在左端</P>
( ?. F( O9 h$ Z; r* r/ B- g+ n<P>if (bin) node[bin].left = v;</P>
<P>node[v].right = bin;</P>
# v* [: t% S1 V! T3 Y4 H<P>bin = v;</P>
<P>}</P>
<P>void Undirected::MoveBins(int bMax, int ToBin, int v)</P>
<P>{// 将顶点v 从其当前所在箱子移动到To B i n .</P>
<P>// v的左、右节点</P>
" ^. u0 d  W5 p<P>int l = node[v].left;</P>
1 p, D5 c, F. W- D. @* A<P>int r = node[v].right;</P>
<P>// 从当前箱子中删除</P>
* z0 e: l/ S7 z; L<P>if (r) node[r].left = node[v].left;</P>
<P>if (l &gt; bMax || bin[l] != v) // 不是最左节点</P>
<P>node[l].right = r;</P>
& J7 Y6 t# y8 O1 `<P>else bin[l] = r; // 箱子l的最左边</P>
% ~) {8 h6 U4 c+ {$ n<P>// 添加到箱子To B i n</P>
<P>I n s e r t B i n s ( ToBin, v);</P>
8 l) A. g0 u6 `+ Z% p<P>}</P>
+ O7 h( e, z3 Y$ L; [2 A! w3 S& S# X<P>函数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 中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的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&gt;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 ]中。</P>
1 H6 i" X. D9 ~5 ]% b9 v$ {6 m2 X, t<P>4. Undirected::BipartiteCover的实现</P>
! S+ p9 I: _- G) F6 I5 e/ K; w; W# O* w<P>函数的输入参数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。</P>
7 y9 S) `) i9 _1 N2 @- J<P>程序13-4 构造贪婪覆盖</P>
5 X- o# v+ j# \; v4 I<P>bool Undirected::BipartiteCover(int L[], int C[], int&amp; m)</P>
1 E5 q; `$ W8 `; [7 G<P>{// 寻找一个二分图覆盖</P>
<P>// L 是输入顶点的标号, L = 1 当且仅当i 在Ａ中</P>
' r  @" R" i7 G- w; a<P>// C 是一个记录覆盖的输出数组</P>
<P>// 如果图中不存在覆盖，则返回f a l s e</P>
: F# W* ^  L# ^1 D! U$ f8 a" t) J<P>// 如果图中有一个覆盖，则返回t r u e ;</P>
& n8 g* Z/ k  b6 x<P>// 在m中返回覆盖的大小; 在C [ 0 : m - 1 ]中返回覆盖</P>
$ p# D2 w3 P: \( h7 P* {7 N4 ]<P>int n = Ve r t i c e s ( ) ;</P>
<P>// 插件结构</P>
<P>int SizeOfA = 0;</P>
4 e- m& |7 s3 _" q! e' k<P>for (int i = 1; i &lt;= n; i++) // 确定集合A的大小</P>
<P>if (L == 1) SizeOfA++;</P>
<P>int SizeOfB = n - SizeOfA;</P>
<P>CreateBins(SizeOfB, n);</P>
0 l6 }8 S$ z7 }  W; H<P>int *New = new int [n+1]; / /顶点i覆盖了Ｂ中N e w [ i ]个未被覆盖的顶点</P>
. N" C( H& I- n: [3 h; R- b<P>bool *Change = new bool [n+1]; // Change为t r u e当且仅当New 已改变</P>
9 s2 A5 ?1 H- i! X<P>bool *Cov = new bool [n+1]; // Cov 为true 当且仅当顶点i 被覆盖</P>
<P>I n i t i a l i z e P o s ( ) ;</P>
<P>LinkedStack<INT> S;</P>
<P>// 初始化</P>
3 A6 z  u4 e+ ~<P>for (i = 1; i &lt;= n; i++) {</P>
6 y& ]7 C& u* }- C7 }& N! S& x<P>Cov = Change = false;</P>
5 B& b( p& ^' s* r3 q' G<P>if (L == 1) {// i 在A中</P>
<P>New = Degree(i); // i 覆盖了这么多</P>
6 \9 p# R4 {, Y& X" y<P>InsertBins(New, i);}}</P>
7 [, r9 ^& B3 r2 h<P>// 构造覆盖</P>
  l! C* x: M" }0 I6 w. O. g<P>int covered = 0, // 被覆盖的顶点</P>
<P>MaxBin = SizeOfB; // 可能非空的最大箱子</P>
  m% z3 l$ N4 I1 \<P>m = 0; // C的游标</P>
; \- R5 m3 @- l' W/ b' Z% @<P>while (MaxBin &gt; 0) { // 搜索所有箱子</P>
9 z8 O  P+ }& z' F4 v" S( f<P>// 选择一个顶点</P>
<P>if (bin[MaxBin]) { // 箱子不空</P>
, ?! f# {/ d3 X% k- e( b' ^<P>int v = bin[MaxBin]; // 第一个顶点</P>
6 z3 v+ {0 m, m1 {# L4 A& Q<P>C[m++] = v; // 把v 加入覆盖</P>
  J% z% v2 a) z8 F3 L<P>// 标记新覆盖的顶点</P>
<P>int j = Begin(v), k;</P>
( D6 A$ H& v5 F- E8 R/ M& I( V0 Q: G<P>while (j) {</P>
. I- d; h& w& d. z* ^7 X; l<P>if (!Cov[j]) {// j尚未被覆盖</P>
3 c" a* w* ~! {) w& b0 Y6 e<P>Cov[j] = true;</P>
2 K/ l' ^8 z, @7 a<P>c o v e r e d + + ;</P>
$ i' E* d' @" ]3 e) z) X* h, n" N<P>// 修改N e w</P>
8 A5 t* o4 z* B% @1 b! q<P>k = Begin(j);</P>
+ }- f% G9 S0 @( x+ V# }0 n1 v$ b$ i<P>while (k) {</P>
<P>New[k]--; // j 不计入在内</P>
<P>if (!Change[k]) {</P>
<P>S.Add(k); // 仅入栈一次</P>
4 A: `2 x, i4 K+ A2 Y/ g; M  p<P>Change[k] = true;}</P>
3 k# u; Q4 o! z. o( e+ H<P>k = NextVe r t e x ( j ) ; }</P>
/ h% k7 b' p8 q4 G$ j<P>}</P>
( w2 T: o  @0 e1 @<P>j = NextVe r t e x ( v ) ; }</P>
<P>// 更新箱子</P>
5 z8 ]4 l# h) D9 u" z5 e1 n1 y6 [<P>while (!S.IsEmpty()) {</P>
<P>S . D e l e t e ( k ) ;</P>
' i, _5 [4 `7 p, d  |<P>Change[k] = false;</P>
( d, U' k; c, f& ^<P>MoveBins(SizeOfB, New[k], k);}</P>
) [' o) ~/ N4 F<P>}</P>
<P>else MaxBin--;</P>
3 H1 f# t& j9 V<P>}</P>
<P>D e a c t i v a t e P o s ( ) ;</P>
4 V% z+ ]0 V# k<P>D e s t r o y B i n s ( ) ;</P>
' l  Y7 d0 k) j  {5 j% `# z! J+ M<P>delete [] New;</P>
# G, r2 M* A' k# X( E% g& t8 L; t<P>delete [] Change;</P>
<P>delete [] Cov;</P>
  o) m: G6 M4 m2 \, z9 U- U; h<P>return (covered == SizeOfB);</P>
$ h9 L4 l# M6 r<P>}</P>
<P>程序1 3 - 4首先计算出集合A和B的大小、初始化必要的双向链表结构、创建三个数组、初始化图遍历器、并创建一个栈。然后将数组C o v和C h a n g e初始化为f a l s e，并将A中的顶点根据它们覆盖B中顶点的数目插入到相应的双向链表中。</P>
% ?8 B1 }8 |: J# v  I* k* s% r0 c<P>为了构造覆盖，首先按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 循环则将这些顶点移到正确的表中。</P>

mengfanqi

<>good!</P>

daomeidan1234

<p>very good</p><p></p>