Algoritmo de Prim
Última actualización
El algoritmo de Prim construye un árbol de expansión mínima (MST) - el conjunto de aristas más barato que conecta todos los nodos sin ciclos - haciendo crecer un único árbol hacia afuera desde un nodo inicial. En cada paso observa todas las aristas que cruzan del árbol a un nodo fuera de él y añade la más barata. Pulsa reproducir arriba para ver cómo se expande el árbol, tomando siempre la arista de menor peso que alcanza un nuevo nodo.
Como siempre elige la arista de cruce mínima, cada adición es segura (garantizada como parte de algún MST). Con una cola de prioridad basada en un montículo binario indexada por la arista más barata hacia cada nodo exterior, Prim se ejecuta en O(E log V). Contrasta con Kruskal, que ordena todas las aristas globalmente en lugar de hacer crecer un único árbol conexo.
Complejidad temporal y espacial
| Implementación | Complejidad | Notas |
|---|---|---|
| Montículo binario | O(E log V) | Cola de prioridad de aristas de cruce |
| Matriz de adyacencia | O(V²) | Más simple; buena para grafos densos |
| Espacio | O(V + E) | Pertenencia al árbol + cola de prioridad |
| Mejor para | Grafos densos | Crece desde un único nodo inicial |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Inicia el árbol con cualquier nodo único. |
| 2 | Observa todas las aristas que cruzan del árbol a un nodo fuera de él. |
| 3 | Elige la arista de cruce con el menor peso. |
| 4 | Añade esa arista y su nuevo nodo al árbol. |
| 5 | Repite hasta que todos los nodos estén en el árbol. |
Ejemplo resuelto
Construyendo el MST de un grafo de 4 nodos con aristas A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, comenzando desde A:
| Paso | Árbol | Aristas de cruce | Arista elegida |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (peso 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (peso 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (peso 4) |
| 4 | {A, B, C, D} | ninguna - todos los nodos en el árbol | listo: peso del MST 1+2+4 = 7 |
Cuándo usar el algoritmo de Prim
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas un árbol de expansión mínima de un grafo conexo, no dirigido y ponderado. | El grafo es dirigido o necesitas caminos más cortos - usa Dijkstra o Bellman-Ford en su lugar. |
El grafo es denso (E cercano a V²); la forma matricial O(V²) es simple y rápida. | El grafo es disperso y las aristas ya están ordenadas o son fáciles de ordenar - Kruskal suele ser más simple. |
| Quieres que el árbol crezca desde una región hacia afuera (p. ej., diseño incremental de una red). | El grafo está desconectado - Prim solo abarca un componente; necesitas un bosque de expansión mínima. |
| Ya tienes una estructura de adyacencia y una cola de prioridad disponibles. | Necesitas detectar ciclos en un conjunto global de aristas - union-find (Kruskal) encaja mejor con esa forma. |
Código de Prim's Algorithm
Una implementación limpia y ejecutable de Prim's Algorithm en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Prim's Algorithm en Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Código de Prim's Algorithm en JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Código de Prim's Algorithm en Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Código de Prim's Algorithm en C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Código de Prim's Algorithm en C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}Preguntas frecuentes sobre el algoritmo de Prim
¿Cuál es la complejidad temporal del algoritmo de Prim?
O(E log V). Una versión más simple con matriz de adyacencia que busca la arista de cruce mínima en cada paso es O(V²), que puede ser más rápida en grafos densos. Ambas usan espacio O(V + E).¿Cuál es la diferencia entre los algoritmos de Prim y Kruskal?
Ambos encuentran un árbol de expansión mínima de forma voraz. Prim hace crecer un único árbol conexo desde un nodo inicial, añadiendo repetidamente la arista más barata que sale del árbol (usando una cola de prioridad). Kruskal considera todas las aristas ordenadas por peso y añade la más barata que no forma un ciclo (usando union-find). Prim suele preferirse en grafos densos, Kruskal en dispersos.
¿El algoritmo de Prim siempre encuentra el MST óptimo?
Sí. En cada paso la arista más barata que cruza el árbol actual es segura de añadir - pertenece a algún árbol de expansión mínima (la propiedad del corte). Añadir repetidamente aristas seguras produce un verdadero árbol de expansión mínima, siempre que el grafo sea conexo.
¿Cuándo debería usar el algoritmo de Prim en lugar del de Kruskal?
O(V²) evita ordenar las E aristas y hace crecer un único árbol desde un nodo inicial. Kruskal destaca en grafos dispersos donde ordenar la lista de aristas es barato y union-find mantiene rápidas las comprobaciones de ciclos. Ambos producen un MST correcto, así que la elección depende sobre todo de la densidad de aristas y de qué estructuras de datos ya tienes.¿El nodo inicial afecta al MST resultante?
No - el peso total del MST es el mismo sin importar desde qué nodo empieces, porque el peso del árbol de expansión mínima de un grafo conexo es único. Las aristas concretas solo pueden diferir cuando varias aristas comparten el mismo peso y existen múltiples MST. De lo contrario, Prim alcanza exactamente el mismo árbol independientemente del nodo inicial.
¿Puede el algoritmo de Prim manejar grafos desconectados?
No directamente. Prim hace crecer un único árbol, así que solo abarca el componente conexo que contiene el nodo inicial y deja el resto sin tocar. Para cubrir cada componente ejecutarías Prim repetidamente desde un nodo no visitado, produciendo un bosque de expansión mínima en lugar de un solo árbol.
Recursos relacionados
Más visualizaciones
