algorithm => polynoom-tijd begrensd algoritme voor Minimum Vertex Cover

Invoering

Dit is een polynoomalgoritme voor het verkrijgen van de minimale hoekpuntdekking van verbonden niet-gerichte grafiek. De tijdcomplexiteit van dit algoritme is O (n2)

parameters

veranderlijk	Betekenis
G	Input verbonden niet-gerichte grafiek
X	Set hoekpunten
C	Laatste reeks hoekpunten

Opmerkingen

Het eerste wat u moet doen in dit algoritme om alle hoekpunten van de grafiek in aflopende volgorde te sorteren op basis van de graad.

Hierna herhaal je ze en voeg je ze toe aan de laatste hoekpuntenset die geen aangrenzend hoekpunt in deze set hebben.

In de laatste fase herhaalt u op de laatste hoekpuntenset en verwijdert u alle hoekpunten met een van de aangrenzende hoekpunten in deze set.

Algoritme Pseudo-code

Algorithm PMinVertexCover (grafiek G)

Invoer verbonden grafiek G

Uitgang Minimale 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 is de minimale hoekpuntdekking van grafiek G

we kunnen bucket-sortering gebruiken voor het sorteren van de hoekpunten op basis van de graad ervan, omdat de maximale waarde van graden (n-1) is, waarbij n het aantal hoekpunten is, dan is de tijdcomplexiteit van de sortering O (n)

Modified text is an extract of the original Stack Overflow Documentation

Licentie onder CC BY-SA 3.0

Niet aangesloten bij Stack Overflow

algorithm
polynoom-tijd begrensd algoritme voor Minimum Vertex Cover

Zoeken…