Aristas del árbol
Longitud total
Aristas revisadas

  • Actual
  • En el árbol
  • Junto al árbol
  • Mejor arista hasta ahora
  • Cerraría un ciclo

Más sobre árboles de expansión mínima

Árbol de expansión mínima

Quieres conectar cada pueblo con cable, cada casa con tuberías de agua o cada ordenador de una red, usando el menor material posible. La respuesta es un árbol de expansión mínima: el conjunto de aristas que conecta todos los nodos con la menor longitud total. Elige el algoritmo de Kruskal o el de Prim y avanza paso a paso para ver crecer el árbol, añadiendo cada vez la arista permitida más corta. 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. Elige el algoritmo: Kruskal prueba las aristas de la más corta a la más larga, Prim hace crecer un solo árbol desde el origen; haz clic en un nodo para que sea el origen de Prim. El número de cada arista es su longitud. Bajo el grafo está la lista de aristas que quedan por probar, o los nodos en espera con la longitud de su mejor arista hacia el árbol. 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

  1. Elige el algoritmo de Kruskal o el de Prim. Para Prim, haz clic en un nodo para que sea el origen.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
  3. Observa cómo las aristas entran en el árbol y crece la longitud total. Nuevo grafo crea otro grafo para probar.

Algoritmo de Kruskal

Ordena todas las aristas de la más corta a la más larga y pruébalas en ese orden. Si una arista une dos trozos que aún no están conectados, entra en el árbol. Si sus dos extremos ya están conectados a través del árbol, cerraría un ciclo, así que se salta. Termina cuando el árbol tiene una arista menos que nodos. Para saber rápido si dos nodos ya están conectados, el algoritmo de Kruskal guarda los trozos en una estructura union-find.

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. Añade una y otra vez el nodo cuya arista es la más corta, junto con esa arista, y revisa sus aristas: alguna puede dar a un vecino un camino más corto hacia el árbol. El algoritmo de Prim se parece al algoritmo de Dijkstra, pero compara aristas sueltas, no distancias enteras desde el origen. Ambos algoritmos terminan siempre con la misma longitud total.

Preguntas frecuentes

¿Qué es un árbol de expansión mínima?

En un grafo conexo cuyas aristas tienen longitudes, un árbol de expansión es un conjunto de aristas que conecta todos los nodos sin ningún ciclo; con n nodos siempre tiene n − 1 aristas. Un árbol de expansión mínima es un árbol de expansión cuya longitud total es la menor posible.

¿Qué diferencia hay entre el algoritmo de Kruskal y el de Prim?

El algoritmo de Kruskal recorre las aristas de todo el grafo de la más corta a la más larga y une trozos separados en un solo árbol. El algoritmo de Prim hace crecer un solo árbol desde un origen, añadiendo siempre la arista más corta que sale de él. Ambos son voraces y encuentran un árbol con la misma longitud total; Kruskal va bien con grafos dispersos, Prim con grafos densos.

¿Es único el árbol de expansión mínima?

Si todas las longitudes de las aristas son distintas, sí. Si algunas son iguales, puede haber varios árboles con el mismo total mínimo, y los algoritmos pueden elegir árboles distintos según cómo deshagan los empates.

¿Es un árbol de expansión mínima lo mismo que los caminos más cortos?

No. El árbol de expansión mínima mantiene pequeña la longitud total de todas las aristas, pero el camino entre dos nodos en el árbol puede ser mucho más largo que su camino más corto. Para caminos más cortos, usa el algoritmo de Dijkstra.

¿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