- Actual
- En el árbol
- Junto al árbol
- Mejor arista hasta ahora
Algoritmo de Prim
El algoritmo de Prim construye un árbol de expansión mínima, el conjunto de aristas más barato que conecta todos los nodos, haciendo crecer un solo árbol desde un origen. En cada paso añade el nodo al que se llega desde el árbol por la arista más corta. Haz clic en un nodo para empezar ahí y avanza paso a paso para ver los nodos en espera, sus mejores aristas y cómo crece el árbol. Pulsa Reproducir para ver crecer el árbol, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Haz clic en un nodo para que sea el origen: el árbol crece desde ahí. El número de cada arista es su longitud. Bajo el grafo están los nodos en espera, cada uno con la longitud de su mejor arista hacia el árbol, que se dibuja discontinua. Nuevo grafo crea otro grafo; elige cuántos nodos y aristas tiene. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Haz clic en un nodo para que sea el origen: el árbol crece desde ahí.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
- Observa los nodos en espera bajo el grafo, cada uno con su mejor arista hacia el árbol. Nuevo grafo crea otro grafo para probar.
Cómo funciona el algoritmo de Prim
Empieza con un árbol de un solo nodo. Cada nodo fuera del árbol recuerda su arista más corta hacia el árbol, si tiene una. Toma una y otra vez el nodo cuya arista es la más corta, añádelo al árbol junto con esa arista y revisa sus aristas: si una es más corta que la mejor arista de un vecino hasta ahora, pasa a ser la mejor arista de ese vecino. Cuando han entrado todos los nodos, el árbol tiene una arista menos que nodos, y su longitud total es la menor posible.
Prim y Dijkstra
El algoritmo de Prim y el algoritmo de Dijkstra son casi iguales: los dos hacen crecer una región desde un origen y guardan los nodos en espera en una cola de prioridad. La diferencia es el número de la cola. Dijkstra guarda la distancia completa de cada nodo desde el origen; Prim solo la longitud de su mejor arista hacia el árbol. Así, Dijkstra construye un árbol de caminos más cortos, y Prim un árbol de longitud total mínima, y los dos árboles suelen ser distintos.
Preguntas frecuentes
¿Qué es el algoritmo de Prim?
Un algoritmo voraz que construye un árbol de expansión mínima de un grafo ponderado haciendo crecer un solo árbol desde un nodo de origen, añadiendo siempre la arista más corta que une el árbol con un nodo de fuera.
¿Importa el nodo de origen?
Solo para el orden: desde cualquier origen, el algoritmo de Prim termina con un árbol de expansión de la misma longitud total mínima. Si algunas aristas tienen la misma longitud, el árbol en sí puede cambiar.
¿Quién inventó el algoritmo de Prim?
Vojtěch Jarník lo describió primero, en 1930. Robert Prim lo redescubrió en 1957 y Edsger Dijkstra en 1959, así que también se llama algoritmo de Jarník o algoritmo de Prim–Jarník.
¿Qué tan rápido es el algoritmo de Prim?
Con un montículo binario, el trabajo crece con E log V para V nodos y E aristas. Con un simple array en lugar de un montículo tarda unos V² pasos, lo que es mejor para grafos densos, donde casi todos los pares de nodos están unidos.
¿Se envía mi grafo a algún sitio?
No. El grafo se crea y el árbol se construye en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor