MST de Prim con un heap

El algoritmo de Prim también encuentra un árbol de expansión mínima, pero hace crecer hacia fuera una única estructura conectada en lugar de ordenar primero todas las aristas. 🌱

Elija cualquier vértice inicial y márquelo como visitado. El árbol comienza con un solo nodo y se expande una arista cada vez.

En cada paso, observe todas las aristas que van del árbol hacia el exterior. Prim siempre toma la más barata de esas aristas de frontera.

Un min-heap permite encontrar rápidamente la arista de frontera más barata. Inserte las aristas candidatas y extraiga la de menor peso en cada ronda.

Extraiga la entrada más pequeña del montículo. Obtendrá el peso y el siguiente vértice más barato que puede conectar al árbol en crecimiento.

Un vértice puede aparecer más de una vez en el montículo. Si extrae uno que ya está visitado, simplemente ignórelo y extraiga otro.

Marque como visitado el vértice extraído y añada su peso al total. Después, inserte sus aristas salientes en el montículo para los pasos siguientes.

Siga extrayendo y expandiendo hasta que todos los vértices estén visitados. En ese momento, el total acumulado es el peso del árbol de expansión mínima.

Cada arista puede insertarse una vez y extraerse una vez, así que Prim basado en un montículo se ejecuta en O(E log V), de forma comparable a Kruskal.

Use Prim en grafos densos con una lista de adyacencia, y Kruskal cuando ya tenga una lista de aristas sencilla. Ambos producen el mismo peso de MST.

El bucle del montículo recuerda al de Dijkstra, pero aquí se comparan los pesos directos de las aristas, no las distancias de los caminos. Reconocer este patrón le ahorra tiempo de programación. ⚡

Construyó un MST con Prim: empiece desde cualquier lugar, use un min-heap para añadir la arista de frontera más barata y omita las visitas obsoletas. ¡Excelente trabajo! 🎉