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

核心提示：例1-13 考察图1 - 6，初始时(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 )=( 6 , 4 , 5 , 6 , 4 )，c语言算法 - 贪婪算法 - 二分覆盖(2)，假设在例1 - 1 2中，第一步选择顶点1 6，因为A的所有顶点都有可能被选择，因此所需步骤数为O

例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)。