algorithm => polynom tidsgränsad algoritm för Minimum Vertex Cover

Introduktion

Detta är en polynomalgoritm för att få det minsta vertexomslaget för ansluten, direktstruerad graf. Tidskomplexiteten för denna algoritm är O (n2)

parametrar

Variabel	Menande
G	Ingång ansluten ostyrd graf
X	Uppsättning av hörn
C	Slutlig uppsättning av vertikaler

Anmärkningar

Det första du måste göra i den här algoritmen för att få alla vertikalerna i diagrammet sorterade i fallande ordning beroende på graden.

Efter det har du iterat på dem och lägg till var och en till den slutliga vertikumsatsen som inte har någon angränsande toppunkt i den här uppsättningen.

I det sista steget upprepas det slutliga toppskäret och ta bort alla topparna som har en av dess intilliggande toppar i denna uppsättning.

Algoritm-pseudokod

Algoritm PMinVertexCover (graf G)

Ange ansluten graf G

Output Minimal vertex Cover Set 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 är den minsta vertexomslaget för graf G

vi kan använda hinksortering för att sortera toppningarna enligt dess grad eftersom det maximala värdet på grader är (n-1) där n är antalet toppningar då sorteringens tidskomplexitet är O (n)

Modified text is an extract of the original Stack Overflow Documentation

Licensierat under CC BY-SA 3.0

Inte anslutet till Stack Overflow

algorithm
polynom tidsgränsad algoritm för Minimum Vertex Cover

Sök…