输入：无向图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.