¿Qué es el Algoritmo de Kruskal?

El algoritmo de Kruskal es un método utilizado para encontrar el Árbol de Expansión Mínima (MST, por sus siglas en inglés) de un grafo ponderado. Selecciona las aristas de menor peso y garantiza que no se formen ciclos al añadirlas al árbol en construcción.

El Código

                
class DisjointSet {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX]++;
      }
    }
  }
}

function kruskal(vertices, edges) {
  const mst = [];
  const disjointSet = new DisjointSet(vertices);

  edges.sort((a, b) => a[2] - b[2]);

  for (const [u, v, weight] of edges) {
    if (disjointSet.find(u) !== disjointSet.find(v)) {
      disjointSet.union(u, v);
      mst.push([u, v, weight]);
    }
  }

  return mst;
}

// Ejemplo de uso
const vertices = 6;
const edges = [
  [0, 1, 4],
  [0, 2, 4],
  [1, 2, 2],
  [1, 0, 4],
  [2, 0, 4],
  [2, 1, 2],
  [2, 3, 3],
  [2, 5, 2],
  [2, 4, 4],
  [3, 2, 3],
  [3, 4, 3],
  [4, 2, 4],
  [4, 3, 3],
  [5, 2, 2],
  [5, 4, 3],
];

console.log("Árbol de expansión mínima:", kruskal(vertices, edges));
                
            

Puntos Clave del Algoritmo

• Entrada: Un grafo ponderado con un conjunto de vértices y aristas.
• Salida: Un conjunto de aristas que forman el Árbol de Expansión Mínima (MST).
• Método:
  • Ordena todas las aristas por peso ascendente.
  • Itera sobre las aristas en orden, añadiendo cada una al MST si no forma un ciclo.
  • Utiliza una estructura de Conjuntos Disjuntos (Disjoint Set) para manejar la conexión de los vértices y evitar ciclos.
• Complejidad:
  • Tiempo: O(E log E), donde E es el número de aristas (debido al ordenamiento).
  • Espacio: O(V), donde V es el número de vértices (para la estructura de Conjuntos Disjuntos).
• Ventajas: Es eficiente para grafos densos y fácil de implementar.
• Desventajas: Requiere un ordenamiento previo de las aristas, lo que puede ser costoso para grafos grandes.

Ejemplo de Ejecución

Grafo inicial:

• Vértices: 6 (numerados del 0 al 5).
• Aristas: [0, 1, 4], [0, 2, 4], [1, 2, 2], [2, 3, 3], [2, 5, 2], [3, 4, 3], [5, 4, 3].

Proceso del algoritmo:

1. Ordena las aristas por peso: [1-2 (2)], [2-5 (2)], [2-3 (3)], [3-4 (3)], [5-4 (3)], ....
2. Añade [1-2] al MST.
3. Añade [2-5] al MST.
4. Añade [2-3] al MST.
5. Añade [3-4] al MST.
6. No añade [5-4] porque formaría un ciclo.

Árbol de expansión mínima:

• Aristas: [1-2, 2-5, 2-3, 3-4]
• Peso total: 10.

Información Adicional

El algoritmo de Kruskal es una herramienta poderosa para encontrar el Árbol de Expansión Mínima, útil en aplicaciones como el diseño de redes, la minimización de costos en infraestructuras y la conexión eficiente de sistemas distribuidos.