Algoritmo de Prim

Definición

• El algoritmo de Prim se utiliza para encontrar el Árbol de Expansión Mínima (MST) de un grafo.
• El grafo debe ser conexo, no dirigido, y sus vértices deben estar etiquetados.
• Las aristas del grafo pueden ser ponderadas.

Conceptos Clave:

• Grafo Conexo: Existe un camino entre cada par de vértices.
• Grafo No Dirigido: Las aristas no tienen dirección.
• Vértices Etiquetados: Cada vértice tiene un nombre que lo diferencia de los demás.
• Aristas Ponderadas: Cada arista tiene un valor de peso.

Pasos del Algoritmo

1. Seleccionar un nodo cualquiera: Por ejemplo, el nodo A.
2. Seleccionar la arista de menor peso incidente al nodo seleccionado: Siendo la única opción de A a B con peso de 8.
3. Repetir el proceso: Continuar seleccionando aristas adyacentes de menor peso siempre que conecten un nodo marcado con uno no marcado.
   • Si hay opciones, seleccionar la de menor peso, por ejemplo: B a C con peso de 4.
4. Evitar ciclos: No seleccionar aristas que formen ciclos en el grafo.

Ejemplo

• Paso 1: Seleccionamos el nodo A.
• Paso 2: La arista menor de A es A-B con peso 8.
• Paso 3: Opciones desde B son B-D (10) y B-C (4). Seleccionamos B-C.
• Paso 4: Desde C, la menor es C-E (2). Seleccionamos C-E.
• Paso 5: Desde E, las opciones son E-F (3) y revisar otros caminos.
• Paso 6: Continúa seleccionando las aristas de menor peso evitando ciclos, hasta completar el árbol.
• Paso Final: Seleccionar la arista hacia el último nodo (H), eligiendo la de menor peso entre las opciones disponibles.

Resultado

• Eliminamos cualquier arista que cree un ciclo.
• El grafo final es el Árbol de Expansión Mínima.