Algoritmo de Kruskal
Última actualización
El algoritmo de Kruskal construye un árbol de expansión mínima (MST): el conjunto de aristas más barato que conecta todos los nodos sin ciclos. Ordena todas las aristas por peso y luego añade con avidez la siguiente arista más barata siempre que una dos nodos que aún no estén conectados. Pulsa reproducir arriba para ver crecer el árbol, una arista segura y barata a la vez.
La comprobación de "¿ya conectados?" se hace con una estructura de datos union-find (conjuntos disjuntos): cada arista se descarta si sus dos extremos ya están en el mismo componente, porque añadirla formaría un ciclo. La ordenación domina el coste, dando O(E log E) en total. Kruskal destaca en grafos dispersos.
Complejidad temporal y espacial
| Medida | Complejidad | Notas |
|---|---|---|
| Tiempo | O(E log E) | Dominado por la ordenación de las aristas |
| Operaciones union-find | ≈ O(E α(V)) | Casi constante por comprobación con compresión de caminos |
| Espacio | O(V + E) | Lista de aristas + estructura de conjuntos disjuntos |
| Mejor para | Grafos dispersos | Funciona a partir de una lista global de aristas |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Ordena cada arista por peso, de forma ascendente. |
| 2 | Coloca cada nodo en su propio componente (union-find). |
| 3 | Toma la siguiente arista más barata. |
| 4 | Si sus extremos están en componentes distintos, añádela al árbol y únelos. |
| 5 | En caso contrario, descártala (crearía un ciclo). |
| 6 | Detente cuando el árbol tenga V − 1 aristas. |
Ejemplo resuelto
Grafo con nodos A, B, C, D y aristas A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). Aristas ordenadas: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| Arista (peso) | Componentes antes | Acción |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | Componentes distintos - añadir al MST, unir a {A,B}. |
B-C(2) | {A,B} {C} {D} | Componentes distintos - añadir al MST, unir a {A,B,C}. |
A-C(3) | {A,B,C} {D} | A y C ya están juntos - descartar (formaría un ciclo). |
C-D(4) | {A,B,C} {D} | Componentes distintos - añadir al MST, unir a {A,B,C,D}. |
| Fin | {A,B,C,D} | El árbol tiene V - 1 = 3 aristas. MST = A-B, B-C, C-D, peso total 7. |
Cuándo usar el algoritmo de Kruskal
| Úsalo cuando | Evítalo cuando |
|---|---|
| El grafo es disperso (pocas aristas respecto a los nodos). | El grafo es denso - Prim con un montículo suele ser más rápido. |
| Las aristas ya están disponibles como una lista global que puedes ordenar. | Las aristas solo llegan mediante listas de adyacencia que debes recorrer por nodo. |
| Quieres una implementación simple respaldada por union-find. | Necesitas que el árbol crezca desde un nodo de inicio concreto. |
| Quieres construir un bosque de expansión de un grafo desconectado. | Debes manejar aristas que llegan en flujo sin una ordenación completa. |
Código de Kruskal's Algorithm
Una implementación limpia y ejecutable de Kruskal's Algorithm en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Kruskal's Algorithm en Python
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)Código de Kruskal's Algorithm en JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Código de Kruskal's Algorithm en Java
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}Código de Kruskal's Algorithm en C++
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}Código de Kruskal's Algorithm en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}Preguntas frecuentes sobre el algoritmo de Kruskal
¿Qué es un árbol de expansión mínima?
Un árbol de expansión mínima (MST) de un grafo ponderado conexo es un subconjunto de aristas que conecta todos los nodos sin ciclos y con el menor peso total posible. Tiene exactamente
V - 1 aristas para V nodos.¿Cuál es la diferencia entre el algoritmo de Kruskal y el de Prim?
Ambos construyen un árbol de expansión mínima de forma voraz. Kruskal ordena todas las aristas globalmente y añade la más barata que no forme un ciclo, usando union-find. Prim hace crecer un único árbol hacia afuera desde un nodo inicial, añadiendo siempre la arista más barata que sale del árbol. Kruskal conviene a grafos dispersos; Prim (con un montículo) a los densos.
¿Por qué el algoritmo de Kruskal usa union-find?
Antes de añadir una arista, Kruskal debe comprobar si sus dos extremos ya están conectados - añadir tal arista crearía un ciclo. Union-find (conjuntos disjuntos) responde a "¿están en el mismo componente?" y fusiona componentes en tiempo amortizado casi constante, lo que mantiene el algoritmo eficiente.
¿Cuándo debería usar el algoritmo de Kruskal en lugar del de Prim?
Prefiere Kruskal cuando el grafo es disperso y ya tienes todas las aristas como una lista que puedes ordenar - la ordenación
O(E log E) es barata cuando E es pequeño. El algoritmo de Prim con un montículo binario o de Fibonacci suele ganar en grafos densos donde E se acerca a V², porque evita ordenar todas las aristas de antemano.¿Funciona el algoritmo de Kruskal en grafos desconectados?
Sí. Si el grafo está desconectado, Kruskal simplemente no puede alcanzar
V - 1 aristas y en su lugar produce un bosque de expansión mínima - un MST por cada componente conexo. Esto surge de forma natural porque union-find nunca fusiona nodos que no tienen camino entre sí.¿Cuál es el error más común al implementar el algoritmo de Kruskal?
Omitir la compresión de caminos y la unión por rango del union-find, lo que degrada cada comprobación de conectividad de casi constante a casi lineal y puede dominar el tiempo de ejecución. Otro error frecuente es olvidar unir realmente los dos componentes tras añadir una arista, lo que permite que aristas posteriores creen ciclos.
Recursos relacionados
Más visualizaciones
