当前位置:牛骨文开发手册数据结构与算法小五的算法学习之路 》 顶点覆盖问题

输入:无向图G(V,E)

输出:C属于V,C中点数最小,满足E中任意一条边中的两个顶点至少有一个在C中

APPROX_Vertex_Cover(G)

1    C=空集

2    E" = E

3    While E" != 空集 Do

4        任选{u,v}属于E"

5        C = C U {u,v}

6        删除E"中所有与u,v相连的边

7    Return C

Ratio Bound(近似比)

设A为算法第四步中选中的边集,由算法第六步可知,A中无邻接边

第五步中每次增加两个节点到C,因此|C| = 2|A|

设C是优化解,则C必须覆盖A

由于A中无邻接边,C*至少包含A中每条边的一个节点,

于是|A|<=|C|,|C| = 2|A| <= 2|C|

即|C| / |C*| <= 2.

因此,算法近似比为2.