Complejidad Temporal
O(V²)
El algoritmo de Prim encuentra un Árbol de Expansión Mínima (MST) para un grafo ponderado, conexo y no dirigido. El MST conecta todos los vértices con el peso total mínimo de aristas.
Cómo funciona:
1. Comenzar con cualquier nodo como árbol inicial
2. Encontrar la arista de peso mínimo que conecte el árbol con un vértice externo
3. Agregar esa arista y vértice al árbol
4. Repetir hasta que todos los vértices estén en el árbol
Complejidad Temporal:
O(V²) con matriz de adyacencia
O(E log V) con min-heap
Complejidad Espacial: O(V)
Aplicaciones:
- Diseño de redes (cableado de costo mínimo)
- Algoritmos de aproximación para problemas NP-duros
- Análisis de clusters
- Segmentación de imágenes
El algoritmo de Prim es un algoritmo voraz que siempre elige la arista más barata para expandir el árbol. Compárese con el algoritmo de Kruskal, que ordena todas las aristas globalmente.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Algoritmo de Prim?
- El algoritmo de Prim encuentra un Árbol de Expansión Mínima (MST) para un grafo ponderado, conexo y no dirigido. El MST conecta todos los vértices con el peso total mínimo de aristas.
- ¿Cuál es la complejidad de Algoritmo de Prim?
- Tiempo (promedio): O(V²) · Espacio: O(V)
- ¿Para quién es este visualizador de Algoritmo de Prim?
- La visualización de Algoritmo de Prim está pensada para nivel avanzado, dentro de la categoría Grafos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Algoritmo de Prim?
- En la misma categoría (Grafos) puedes explorar: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Todos tienen visualización interactiva.