¿Qué es el algoritmo de Prims?

El algoritmo de Prim ayuda a encontrar el arbol de expansión mínimo de un grafico . Determina el subconjunto de bordes que incluyen cada vértice de la gráfica. También reduce las sumas de los pesos de los bordes. 

Además, este algoritmo comienza con el nodo raíz y comprueba todos los nodos adyacentes, incluidos todos los bordes de conexión en cada paso. 

Además, selecciona los bordes con menos pesos que no causan ciclos.

Los pasos del algoritmo son los siguientes.

Paso 1 - Seleccione un vértice inicial o un vértice raíz

Paso 2: repite los pasos 3 y 4 hasta que haya vértices de franja

Paso 3: seleccione un borde que conecte el vértice del árbol y el vértice marginal que tenga un peso mínimo

Paso 4: agregue el borde seleccionado y el vértice al árbol de expansión mínimo

 

(0 votes)