Prim construye un árbol de expansión mínima haciendo crecer una única región conectada. En cada paso incorpora la arista más barata que une el árbol actual con un vértice exterior.
El algoritmo de Prim resuelve el problema del árbol de expansión mínima en grafos no dirigidos, conectados y ponderados. Comienza desde cualquier vértice y agrega una conexión por vez.
La selección siempre conserva un único árbol: cada nueva arista conecta un vértice incluido con otro que todavía se encuentra fuera.
La frontera está formada por las aristas con exactamente un extremo dentro del árbol actual.
Las aristas con ambos extremos dentro se descartan porque crearían un ciclo. Las que tienen ambos extremos fuera todavía no conectan con el árbol.
Los vértices incluidos y los no incluidos forman un corte. La propiedad del corte garantiza que una arista de peso mínimo que lo cruza es segura para algún MST.
Prim aplica esta propiedad repetidamente. Después de incorporar la arista segura, el corte cambia y se calcula una nueva frontera.
Prim puede comenzar en cualquier vértice. El costo mínimo final será el mismo, aunque el orden de selección y el MST obtenido pueden cambiar cuando existen empates.
Selecciona un nodo como origen antes de iniciar. Avanza para observar el árbol, la frontera ordenada por peso y la arista mínima elegida en cada corte.
Vértices incluidos
Frontera ordenada
Acción actual
Celeste indica el árbol construido, verde las aristas de frontera y rosa la arista elegida en el paso actual.
Si el árbol contiene A y B, y la frontera ofrece A—C con peso 5, B—C con peso 2 y B—D con peso 4, Prim elige B—C.
Después de incorporar C se eliminan de la frontera las conexiones que ahora tienen ambos extremos dentro y se agregan las aristas que salen de C hacia vértices exteriores.
Una versión matricial mantiene para cada vértice exterior el costo de su conexión más barata al árbol.
function primMatriz(matriz, origen = 0) {
const n = matriz.length;
const incluido = Array(n).fill(false);
const clave = Array(n).fill(Infinity);
const padre = Array(n).fill(-1);
clave[origen] = 0;
for (let paso = 0; paso < n; paso++) {
let u = -1;
for (let v = 0; v < n; v++) {
if (!incluido[v] && (u === -1 || clave[v] < clave[u])) u = v;
}
if (u === -1 || clave[u] === Infinity) break;
incluido[u] = true;
for (let v = 0; v < n; v++) {
const peso = matriz[u][v];
if (!incluido[v] && peso !== null && peso < clave[v]) {
clave[v] = peso;
padre[v] = u;
}
}
}
return padre;
}Con listas de adyacencia, una cola de prioridad guarda las mejores conexiones conocidas hacia los vértices exteriores. La entrada de menor peso se extrae primero.
Cuando aparecen varias entradas para un mismo vértice, las desactualizadas se descartan si el nodo ya fue incluido.
function prim(grafo, origen, cola) {
const incluidos = new Set();
const aristasMST = [];
let costo = 0;
cola.insertar({ peso: 0, desde: null, hasta: origen });
while (!cola.estaVacia()) {
const arista = cola.extraerMinimo();
if (incluidos.has(arista.hasta)) continue;
incluidos.add(arista.hasta);
if (arista.desde !== null) {
aristasMST.push(arista);
costo += arista.peso;
}
for (const vecino of grafo[arista.hasta]) {
if (!incluidos.has(vecino.destino)) {
cola.insertar({
peso: vecino.peso,
desde: arista.hasta,
hasta: vecino.destino
});
}
}
}
return { aristasMST, costo, completo: incluidos.size === Object.keys(grafo).length };
}Cada arista elegida tiene exactamente un extremo dentro del árbol. El otro extremo es un vértice nuevo.
Si ambos extremos ya estuvieran incluidos, la arista se descartaría.
Desde un origen, Prim solo puede cubrir su componente. Si la cola se vacía antes de incluir todos los vértices, el grafo no tiene un árbol generador global.
Para obtener un bosque mínimo se reinicia Prim desde cada vértice todavía no incluido.
Si varias aristas de la frontera comparten el peso mínimo, cualquiera es segura. La elección puede producir árboles diferentes con el mismo costo.
Para obtener resultados reproducibles se puede desempatar por identificador del origen, destino o posición original de la arista.
Ambos hacen crecer un conjunto desde un origen y utilizan una cola de prioridad, pero sus prioridades representan objetivos diferentes.
| Algoritmo | Prioridad | Objetivo |
|---|---|---|
| Prim | Peso de la arista que conecta al árbol | Minimizar costo total de conexión |
| Dijkstra | Distancia total desde el origen | Minimizar cada ruta desde el origen |
| Característica | Prim | Kruskal |
|---|---|---|
| Estructura que crece | Un árbol | Un bosque |
| Selección | Mínima de la frontera | Mínima global que no crea ciclo |
| Estructura auxiliar | Cola de prioridad | Union-Find |
| Suele convenir | Grafos densos | Grafos dispersos o lista de aristas |
| Representación | Implementación | Tiempo |
|---|---|---|
| Matriz de adyacencia | Búsqueda lineal | O(V²) |
| Lista de adyacencia | Montículo binario | O(E log V) |
La versión matricial puede ser excelente en grafos densos, donde E se aproxima a V².
Prim convierte la propiedad del corte en un procedimiento concreto: mantiene un árbol conectado y lo amplía mediante la opción más barata disponible. Su implementación con cola de prioridad resulta eficiente y natural.
En el próximo tema estudiaremos Kruskal, que ordena globalmente las aristas y une componentes sin crear ciclos.