algorithm
algorytm związany z czasem wielomianowym dla minimalnej osłony wierzchołków

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

Wprowadzenie

Jest to algorytm wielomianowy służący do uzyskania minimalnego pokrycia wierzchołków połączonego niekierowanego wykresu. Złożoność czasowa tego algorytmu wynosi O (n2)

Parametry

Zmienna	Znaczenie
sol	Wejściowy podłączony niekierowany wykres
X	Zestaw wierzchołków
do	Ostateczny zestaw wierzchołków

Uwagi

Pierwszą rzeczą, którą musisz zrobić w tym algorytmie, aby posortować wszystkie wierzchołki wykresu w porządku malejącym według jego stopnia.

Następnie wykonujesz iterację i dodajesz każdy z nich do końcowego zestawu wierzchołków, które nie mają żadnych sąsiadujących wierzchołków w tym zestawie.

W ostatnim etapie iteruj na końcowym zestawie wierzchołków i usuń wszystkie wierzchołki, które mają jeden z sąsiednich wierzchołków w tym zestawie.

Pseudo-kod algorytmu

Algorytm PMinVertexCover (wykres G)

Wprowadź podłączony wykres G

Zestaw minimalnej wyjściowej osłony wierzchołków 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 jest minimalnym pokryciem wierzchołka wykresu G

możemy użyć sortowania kubełkowego do sortowania wierzchołków według jego stopnia, ponieważ maksymalna wartość stopni wynosi (n-1), gdzie n jest liczbą wierzchołków, wówczas złożoność czasowa sortowania będzie wynosić O (n)

Modified text is an extract of the original Stack Overflow Documentation

Licencjonowany na podstawie CC BY-SA 3.0

Nie związany z Stack Overflow