algorithm
Algoritmo limitato al tempo polinomiale per la copertura del vertice minimo

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language

introduzione

Questo è un algoritmo polinomiale per ottenere la copertura minima di vertice del grafo indiretto connesso. La complessità temporale di questo algoritmo è O (n2)

Parametri

Variabile	Senso
sol	Ingresso collegato grafico non diretto
X	Insieme di vertici
C	Set finale di vertici

Osservazioni

La prima cosa che devi fare in questo algoritmo per ottenere tutti i vertici del grafico ordinati in ordine decrescente in base al suo grado.

Dopo di ciò si ha iterato su di essi e si aggiunge ognuno al set di vertici finali che non hanno alcun vertice adiacente in questo set.

Nello stadio finale, itera sui vertici finali impostati e rimuovi tutti i vertici che hanno uno dei suoi vertici adiacenti in questo set.

Algoritmo Pseudo codice

Algoritmo PMinVertexCover (grafico G)

Ingresso collegato al grafico G

Uscita Copri vertice minimo 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 è la copertura del vertice minimo del grafico G

possiamo usare bucket sort per ordinare i vertici in base al suo grado perché il valore massimo dei gradi è (n-1) dove n è il numero di vertici, quindi la complessità temporale dell'ordinamento sarà O (n)

Modified text is an extract of the original Stack Overflow Documentation

Autorizzato sotto CC BY-SA 3.0

Non affiliato con Stack Overflow