Este es un algoritmo polinomial para obtener la cobertura mínima de vértice de un gráfico no dirigido conectado. La complejidad temporal de este algoritmo es O (n2).
Variable | Sentido |
---|---|
sol | Entrada conectada grafica no dirigida |
X | Conjunto de vértices |
do | Conjunto final de vértices |
Lo primero que debe hacer en este algoritmo para obtener todos los vértices de la gráfica ordenados en orden descendente según su grado.
Después de eso, hay que iterar en ellos y agregar cada uno al conjunto de vértices finales que no tienen ningún vértice adyacente en este conjunto.
En la etapa final, itere en el conjunto de vértices finales y elimine todos los vértices que tengan uno de sus vértices adyacentes en este conjunto.