Introducción

El algoritmo de Kruskal (1956) es uno de los métodos clásicos para encontrar un Árbol de Expansión Mínima (MST) en un grafo no dirigido y ponderado. A diferencia del algoritmo de Prim, Kruskal trabaja sobre aristas ordenadas por peso y utiliza una estructura de Union‑Find (Disjoint Set) para evitar ciclos.

Este algoritmo es especialmente útil cuando el grafo es disperso (pocas aristas comparado con el número de vértices) o cuando se dispone de todas las aristas de antemano, por ejemplo en:

• Diseño de redes de telecomunicaciones.
• Planificación de rutas de distribución de energía.
• Clustering jerárquico en machine learning.

Complejidad y análisis de rendimiento

La complejidad del algoritmo depende de dos factores principales:

• Ordenación de aristas: O(E log E) (usualmente O(E log V) porque E ≤ V²).
• Operaciones de Union‑Find con compresión de caminos y unión por rango: α(V) (función inversa de Ackermann), prácticamente constante.

En la práctica, Kruskal es más rápido que Prim en grafos muy esparcidos, mientras que Prim gana en grafos densos donde E ≈ V².

Implementación paso a paso en Python

A continuación se muestra una implementación clara y optimizada usando la biblioteca estándar. Se incluye la clase DisjointSet con compresión de caminos y unión por rango.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        # Compresión de caminos
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False  # Ya están conectados, ciclo
        # Unión por rango
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:
            self.parent[yr] = xr
            self.rank[xr] += 1
        return True
def kruskal(edges, n_vertices):
    """Devuelve el MST como lista de aristas (u, v, peso)."""
    # 1. Ordenar aristas por peso ascendente
    edges = sorted(edges, key=lambda e: e[2])
    ds = DisjointSet(n_vertices)
    mst = []
    for u, v, w in edges:
        if ds.union(u, v):
            mst.append((u, v, w))
        if len(mst) == n_vertices - 1:
            break
    return mst
    

El algoritmo es determinista y fácil de adaptar a estructuras externas como networkx o pandas.

Ejemplo práctico: cálculo del MST de una red de ciudades

Supongamos que tenemos cinco ciudades conectadas por carreteras con los siguientes costos (kilómetros):

# Vértices: 0‑A, 1‑B, 2‑C, 3‑D, 4‑E
edges = [
    (0, 1, 10), (0, 2, 20), (0, 3, 30),
    (1, 2, 25), (1, 4, 15),
    (2, 3, 35), (2, 4, 5),
    (3, 4, 12)
]
mst = kruskal(edges, 5)
print("Árbol de expansión mínima:")
for u, v, w in mst:
    print(f"{u} – {v} : {w}")
    

Salida esperada:

Árbol de expansión mínima:
2 – 4 : 5
0 – 1 : 10
3 – 4 : 12
0 – 2 : 20
    

El costo total del MST es 47 (5+10+12+20).

Uso de Kruskal con networkx

Si ya trabajas con networkx, puedes delegar la lógica a la función incorporada minimum_spanning_tree que, por defecto, emplea Kruskal. Sin embargo, entender la implementación propia permite personalizar criterios (por ejemplo, excluir aristas temporales).

import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from(edges)
# networkx usa Kruskal internamente cuando el grafo es esparcido
mst_nx = nx.minimum_spanning_tree(G, algorithm='kruskal')
print(list(mst_nx.edges(data='weight')))
    

Esto devuelve exactamente el mismo conjunto de aristas que la versión manual.

Buenas prácticas, optimización y troubleshooting

• Pre‑procesado de datos: Verifica que no haya aristas duplicadas con pesos diferentes; si existen, mantén la de menor peso.
• Memoria: Para grafos con millones de aristas, almacena la lista como numpy.ndarray o pandas.DataFrame y usa np.argsort para ordenar sin crear copias.
• Paralelismo: La fase de ordenación puede paralelizarse con multiprocessing o dask. La unión de conjuntos sigue siendo secuencial por dependencia.
• Detección de ciclos inesperados: Si el MST tiene menos de V‑1 aristas, el grafo está desconectado. En ese caso, Kruskal produce un bosque de expansión mínima y deberás manejar componentes aislados.
• Seguridad: Cuando el algoritmo se ejecuta sobre datos externos, sanitiza los índices de vértices para evitar IndexError o ataques de denegación de servicio mediante grafos extremadamente densos.

Casos de uso avanzados y extensiones

El algoritmo de Kruskal sirve como base para técnicas más sofisticadas:

• Clustering jerárquico (single‑link): Al detener la unión antes de alcanzar V‑1 aristas, los componentes resultantes forman clusters.
• Redes de distribución de energía: Permite planificar líneas de transmisión minimizando costos de instalación.
• Generación de mazos de pruebas: Al crear grafos aleatorios y extraer su MST, se obtienen casos de prueba con propiedades estructurales conocidas.

Conclusión

El algoritmo de Kruskal sigue siendo una herramienta esencial para resolver problemas de optimización en grafos. Su sencilla lógica basada en ordenación y la estructura Union‑Find lo hacen fácil de implementar, escalar y adaptar a entornos de producción modernos, especialmente cuando se combina con bibliotecas como networkx o pandas. Aplicando las buenas prácticas descritas, podrás manejar grafos de gran tamaño manteniendo un rendimiento cercano a O(E log V) y una huella de memoria mínima.