Introduction

¡Bienvenido al curso final de la serie Algoritmos de Grafos! Al igual que Kruskal, el Algoritmo de Prim construye un Árbol de Recubrimiento Mínimo: el conjunto de aristas más económico que conecta cada vértice sin formar un ciclo. Los dos algoritmos llegan a la misma respuesta por rutas diferentes.

Prim hace crecer el árbol hacia afuera desde un vértice inicial. En cada paso, añade la arista individual más económica que conecta el árbol con un vértice que aún no está en él.

El grafo es no dirigido y ponderado, dado como n (vértices 0 a n - 1) y edges, un array plano de triples [u0, v0, w0, ...] para una arista no dirigida u - v de peso w. Comenzamos desde el vértice 0.

¡Terminemos la serie!