Aristas del árbol
Longitud total
Aristas revisadas

  • Actual
  • En el árbol
  • Cerraría un ciclo

Más sobre el algoritmo de Kruskal

Algoritmo de Kruskal

El algoritmo de Kruskal construye un árbol de expansión mínima, el conjunto de aristas más barato que conecta todos los nodos, de la forma más sencilla que cabe imaginar: toma las aristas de la más corta a la más larga y se queda con cada una salvo que cierre un ciclo. Avanza paso a paso para ver cómo trozos separados crecen y se funden en un solo árbol, y qué aristas se saltan. 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. El número de cada arista es su longitud. Bajo el grafo están las aristas que quedan por probar, de la más corta a la más larga; una arista cuyos extremos ya están conectados cerraría un ciclo y se dibuja discontinua en rojo. 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. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso.
  2. Arrastra el control de pasos para saltar a cualquier punto. Las aristas que quedan por probar aparecen bajo el grafo, de la más corta a la más larga.
  3. Fíjate en las aristas discontinuas en rojo: cerrarían un ciclo. Nuevo grafo crea otro grafo para probar.

Cómo funciona el algoritmo de Kruskal

Ordena todas las aristas de la más corta a la más larga. Al principio, cada nodo es un trozo por sí solo. Prueba las aristas en orden: si una arista une dos trozos distintos, entra en el árbol y los dos trozos pasan a ser uno; si sus dos extremos ya están en el mismo trozo, cerraría un ciclo, así que se salta. Termina cuando todo es un solo trozo, lo que ocurre tras una arista menos que nodos, a menudo mucho antes de probar la última arista.

Union-find

Para cada arista, el algoritmo de Kruskal tiene que preguntar si sus dos extremos ya están conectados. Una estructura union-find lo responde rápido: cada trozo tiene un nodo representante, find sigue los enlaces hasta él, y union enlaza un representante con el otro. Con dos trucos sencillos, la compresión de caminos y la unión por tamaño, cada pregunta tarda un tiempo casi constante, así que ordenar las aristas es la parte más lenta, con un trabajo que crece con E log E.

Preguntas frecuentes

¿Qué es el algoritmo de Kruskal?

Un algoritmo voraz que construye un árbol de expansión mínima ordenando todas las aristas de la más corta a la más larga y añadiendo cada arista que no cierra un ciclo con las aristas ya elegidas.

¿Cómo detecta un ciclo el algoritmo de Kruskal?

Una arista cierra un ciclo justo cuando sus dos extremos ya están conectados por aristas elegidas. Una estructura union-find lleva la cuenta de qué nodos están conectados y responde a esa pregunta casi al instante.

¿Por qué funciona el algoritmo de Kruskal?

Por la propiedad del ciclo: la arista más larga de un ciclo nunca hace falta para un árbol de expansión mínima. Cada arista que Kruskal salta es la más larga del ciclo que cerraría, ya que todas las aristas anteriores eran más cortas o iguales.

¿Cuándo usar Kruskal en lugar de Prim?

El algoritmo de Kruskal es sencillo y rápido en grafos dispersos, y trabaja directamente sobre una simple lista de aristas. El algoritmo de Prim va bien con grafos densos y con grafos guardados como listas de adyacencia. Los dos encuentran un árbol de la misma longitud total.

¿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