algorithm
полиномиально ограниченный алгоритм для минимальной вершины

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

Вступление

Это полиномиальный алгоритм для получения минимального вершинного покрытия связанного неориентированного графа. Сложность времени этого алгоритма O (n2)

параметры

переменная	Имея в виду
г	Ввод подключенного ненаправленного графика
Икс	Набор вершин
С	Конечный набор вершин

замечания

Первое, что вам нужно сделать в этом алгоритме, чтобы получить все вершины графа, отсортированные по убыванию в зависимости от степени.

После этого вы выполняете итерацию по ним и добавляете каждый из них в конечные вершины, которые не имеют соседних вершин в этом наборе.

В завершающей стадии итерации на конечном наборе вершин и удалим все вершины, которые имеют одну из своих смежных вершин в этом множестве.

Алгоритм Псевдокод

Алгоритм PMinVertexCover (граф G)

Ввод связанного графа G

Минимальный набор вершинной вершины 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 - минимальное вершинное накрытие графа G

мы можем использовать сортировку ведра для сортировки вершин в соответствии с его степенью, поскольку максимальное значение степеней (n-1), где n - количество вершин, тогда сложность времени сортировки будет равна O (n)

Modified text is an extract of the original Stack Overflow Documentation

Лицензировано согласно CC BY-SA 3.0

Не связан с Stack Overflow