Introduction
Lección 1 de 9 del curso Algoritmo de Kruskal - Algoritmos de grafos de Coddy.
¡Bienvenido de nuevo a la serie de Algoritmos de Grafos! Un Árbol de Recubrimiento Mínimo (MST) conecta cada vértice de un grafo ponderado utilizando el peso total de aristas más económico posible, sin ciclos.
El Algoritmo de Kruskal construye el MST de forma voraz (greedy): ordena las aristas de la más barata a la más cara y añade cada una, siempre que no cree un ciclo. El truco para detectar ciclos rápidamente es una estructura de datos llamada union-find (también conocida como conjunto disjunto).
El grafo es no dirigido y ponderado, dado como n (vértices 0 a n - 1) y edges, un array plano de triples [u0, v0, w0, ...] para una arista no dirigida u - v de peso w.
¡Empecemos!
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
