Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Graph Algorithms Visualizer

Prim's MST

Time O(E log V) · Space O(V)
Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Visited 0
Frontier 0
Status Ready
Unvisited
Start
Active
Visited
MST / SPT
Rejected
SCC component

Queue

Step Explanation

Select an algorithm and press Play to begin.

Pseudocode 
 
 
 
 
  
 
 
Prim's Minimum Spanning Tree
  
 
  Intermediate (3/5)
 
~1 hora   Minimum Spanning Tree (MST)  Cut property  Greedy: cheapest edge to unvisited  Priority queue / min-heap  
Prereqs: Grafos ponderados, Colas de prioridad  
 
Quick Reference
Prim's Algorithm
Prim's algorithm finds a Minimum Spanning Tree (MST) for a weighted undirected graph by growing a tree one vertex at a time from an arbitrary start, always adding the cheapest edge that connects a tree vertex to a non-tree vertex.

Difficulty: Intermediate (3/5)
graph
Complexity
Best Time
O((V + E) log V)
Average Time
O((V + E) log V)
Worst Time
O((V + E) log V)
Space
O(V)
When to Use
Use Prim's when you need a minimum spanning tree for a dense graph, or when you have an adjacency matrix representation.
Pros
  • Finds the MST efficiently with a binary heap
  • Works well on dense graphs
  • Simple greedy approach with proven optimality
Cons
  • Only works on undirected graphs
  • Requires priority queue for efficiency
  • Not as performant as Kruskal on sparse graphs
History
Prim's algorithm was first discovered by Vojtěch Jarník in 1930, independently rediscovered by Robert C. Prim in 1957, and later by Edsger W. Dijkstra in 1959.
 
 
Prim’s algorithm construye un Minimum Spanning Tree (MST) expandiendo desde un nodo fuente, siempre añadiendo la arista más barata que conecta el árbol actual con un nodo nuevo. Es el algoritmo greedy de referencia para MST.


Funciona como crecer un árbol desde una semilla: mantienes un min-heap de aristas candidatas (cortes) y extraes la más barata que conecta con un nodo no visitado.


Cómo Funciona


    

  1. Inicializa: nodo fuente en el MST, dist[v] = ∞ para los demás.
    2. 

  2. Procesa el nodo con dist mínimo no visitado.
    3. 

  3. Relaja todas sus aristas: actualiza dist[vecino] si la arista es más barata.
    4. 

  4. Repite hasta visitar todos los nodos.
    5. 



Idea Clave


La cut property es la garantía: en cualquier corte del grafo (división en dos conjuntos), la arista más barata que cruza el corte pertenece a algún MST. Prim siempre elige esa arista más barata para expandir el árbol.


El min-heap garantiza que extraes la arista más barata en O(log V), haciendo el total O(E log V).


Ejemplo Trabajado


Grafo:


A--B(2)   B--C(3)
|  \     |   \
4   1    1    4
|    \   |    \
D--C(5) D--E(2)


Fuente = A:


    

  1. A (dist=0) → vecinos: B=1, D=4. Heap: [(1,B), (4,D)]
    2. 

  2. Extrae B (1) → MST: {A-B}. Vecinos: C=3, D=1+1=2 (mejora de 4 a 2). Heap: [(2,D), (3,C)]
    3. 

  3. Extrae D (2) → MST: {A-B, B-D}. Vecinos: C=2+5=7 (no mejora), E=2+2=4. Heap: [(3,C), (4,E)]
    4. 

  4. Extrae C (3) → MST: {A-B, B-D, B-C}. Vecinos: E=3+4=7 (no mejora). Heap: [(4,E)]
    5. 

  5. Extrae E (4) → MST completo.
    6. 



Resultado: MST edges = {A-B, B-D, B-C, D-E} con peso total 1+1+3+2 = 7.


Casos Extremos y Trampas


    

  • Grafo disperso — O(E log V) es cercano a lineal.
    • 

  • Grafo denso — O(V²) con array simple puede ser mejor que O(E log V) con heap.
    • 

  • Múltiples MST — si hay empates, Prim puede retornar cualquiera; todos tienen el mismo peso total.
    • 

  • Grafo no conexo — Prim solo cubre el componente de la fuente. Para MST completo, itera sobre todos los componentes.
    • 



Comparación con Kruskal
































AspectoPrimKruskal
EstrategiaCrece árbol desde semillaOrdena aristas, añade seguras
Denso O(V²)Array simpleO(E log E) dominado
DispersoO(E log V)O(E log E) ≈ O(E log V)
Natural paraGrafos representados como adjacency listGrafos dispersos, edge list


Aplicaciones


    

  • Redes de computadoras — diseño de backbone con costo mínimo
    • 

  • Circuitos eléctricos — cableado mínimo que conecta todos los puntos
    • 

  • Clusterización — single-linkage clustering
    • 

  • Enseñanza — introduce cut property y greedy en grafos
    • 



Trayectoria de Práctica


    

  1. Ejecuta Prim desde nodo A en el visualizador; registra el heap después de cada extracción.
    2. 

  2. Demuestra la cut property en un grafo pequeño: muestra que la arista más barata del corte siempre está en algún MST.
    3. 

  3. Compara complejidad con array vs heap para V=100, E=500.
    4. 

  4. ¿Por qué Prim es más natural para grafos densos que Kruskal?
    5. 

  5. Investiga Borůvka’s algorithm: ¿cómo combina Prim paralelo?
    6.