Saltar al contenido principal
Data structures, algorithms, and the core CS foundations — plus an optional advanced track for expert topics.

Core Computer Science

Data structures, algorithms, and the core CS foundations — plus an optional advanced track for expert topics.

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 
 
 
 
 
  
 
 
Minimum Spanning Tree (MST)
   
 
  Intermediate (3/5)
 
~1 hora   Spanning tree: conecta todos los nodos sin ciclos  Minimum: minimize total edge weight  Cut property  Prim y Kruskal  
Prereqs: Grafos ponderados, Union-Find, 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.
 
 
Minimum Spanning Tree (MST) es un subgrafo que conecta todos los vértices de un grafo conexo con el mínimo peso total, sin ciclos y con exactamente V-1 aristas.


Es uno de los problemas más importantes en teoría de grafos con aplicaciones directas en diseño de redes, clustering, y aproximaciones de problemas NP-hard.


Propiedades Clave


Cut Property


En cualquier corte del grafo (división en dos conjuntos), la arista de menor peso que cruza el corte pertenece a algún MST.


Eso es la base de Prim: cada paso elige la arista más barata que expande el árbol.


Cycle Property


En cualquier ciclo, la arista de mayor peso no pertenece a ningún MST.


Eso es la base de Kruskal: cada paso añade la arista más barata que no forma ciclo.


Algoritmos


Prim


    

  • “Crece un árbol desde un nodo fuente.
    • 

  • Usa min-heap de aristas candidatas.
    • 

  • Complejidad: O((V+E) log V).
    • 



Kruskal


    

  • Ordena aristas por peso.
    • 

  • Usa Union-Find para evitar ciclos.
    • 

  • Complejidad: O(E log E) ≈ O(E log V).
    • 



Comparación

























AlgoritmoEstrategiaEstructuraComplejidad
PrimCrece árbolMin-heapO((V+E) log V)
KruskalOrdena aristasDSUO(E log E)


Cuándo Usar Cada Uno


    

  • Prim: grafos densos, adjacency list, necesitas MST desde nodo específico.
    • 

  • Kruskal: grafos dispersos, edge list, fácil de paralelizar (ordena aristas independientes).
    • 



Casos Extremos


    

  • Grafo completo — E = V(V-1)/2, Prim con array O(V²) puede ser mejor que heap.
    • 

  • Grafo disperso — Kruskal domina.
    • 

  • Múltiples MST — si hay empates, cualquier árbol de peso mínimo es válido.
    • 

  • Grafo no conexo — no existe MST; obtienes un Minimum Spanning Forest.
    • 



Aplicaciones


    

  • Diseño de redes — cableado mínimo, redes de computadoras
    • 

  • Clusterización — single-linkage hierarchical clustering
    • 

  • Approximaciones — Traveling Salesman Problem approximation (2-approx)
    • 

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



Trayectoria de Práctica


    

  1. Implementa Prim y Kruskal; compara en el mismo grafo.
    2. 

  2. Verifica cut property en un grafo pequeño.
    3. 

  3. ¿Por qué Kruskal es más fácil de paralelizar?
    4. 

  4. Investiga Borůvka: algoritmo paralelo original para MST.
    5. 

  5. Investiga aproximación TSP: ¿por qué MST da 2-approx?
    6. 



”