算法伪代码

算法 PMinVertexCover（图 G）

输入连接图 G

输出最小顶点覆盖集 C

Set C <- new Set<Vertex>() 

Set X <- new Set<Vertex>() 

X <- G.getAllVerticiesArrangedDescendinglyByDegree()

for v in X do
    List<Vertex> adjacentVertices1 <- G.getAdjacent(v)

    if !C contains any of adjacentVertices1 then
        
        C.add(v)

for vertex in C do

    List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)

    if C contains any of adjacentVertices2 then
        
        C.remove(vertex)

        
return C

C 是图 G 的最小顶点覆盖

我们可以使用桶排序根据其度数对顶点进行排序，因为度的最大值是（n-1），其中 n 是顶点数，那么排序的时间复杂度将是 O(n)