algorithm => Polynom-Zeit-begrenzter Algorithmus für Minimum Vertex Cover

Einführung

Dies ist ein Polynomalgorithmus, um die minimale Scheitelpunktdeckung eines verbundenen ungerichteten Graphen zu erhalten. Die zeitliche Komplexität dieses Algorithmus ist O (n2)

Parameter

Variable	Bedeutung
G	Eingabe verbundener nicht gerichteter Graph
X	Satz von Eckpunkten
C	Endgültiger Satz von Scheitelpunkten

Bemerkungen

Das erste, was Sie in diesem Algorithmus tun müssen, um alle Scheitelpunkte des Graphen in absteigender Reihenfolge nach Grad zu sortieren.

Danach müssen Sie sie iterieren und jeden zu den endgültigen Vertices setzen, die keinen benachbarten Vertex in dieser Menge haben.

In der letzten Phase iterieren Sie die letzten Scheitelpunkte und entfernen Sie alle Scheitelpunkte, die einen ihrer benachbarten Scheitelpunkte in diesem Satz haben.

Algorithmus-Pseudo-Code

Algorithmus PMinVertexCover (Graph G)

Eingebundener Graph G

Minimaler Scheitelüberdeckungssatz für Ausgabe 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 ist die minimale Scheitelpunktabdeckung von Graph G

Wir können Bucket-Sortierung verwenden, um die Scheitelpunkte nach ihrem Grad zu sortieren, da der Maximalwert von Grad (n-1) ist.

Modified text is an extract of the original Stack Overflow Documentation

Lizenziert unter CC BY-SA 3.0

Nicht angeschlossen an Stack Overflow

algorithm
Polynom-Zeit-begrenzter Algorithmus für Minimum Vertex Cover

Suche…