← Volver a los ejercicios

Kruskal línea por línea

Se ejecuta kruskal paso a paso. El número que acompaña a cada línea es el de su archivo y el contador dice cuántas veces se ejecuta.

1. El grafo y la predicción

Grafo:

En orden de peso

¿Cuántas aristas se descartan por cerrar ciclo?
¿En qué puesto de la lista ordenada se completa el árbol?

2. Ejecute el código

Paso 0 de 0
Decisión
En ámbar, la arista en turno. Verde: entró. Gris punteada: cerraba ciclo.
Lista ordenada

3. Los conjuntos disjuntos

Pedazos
mst
p cambia dos veces: cuando union cuelga una raíz de la otra y cuando find_set acorta el camino que recorrió.

4. Lo que quedó

5. Para llevarse

En el grafo de ocho vértices, baje el peso de 0–2 de 7 a 1. Diga cuál arista sale del árbol, cuánto pesa el nuevo y en qué puesto se completa. Después construya un grafo de seis vértices en el que se descarten tres aristas seguidas antes de completar el árbol.