輸入：無向圖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.