Ya hemos discutido dos algoritmos de técnicas codiciosas en nuestros artículos anteriores y en este artículo, entenderemos brevemente el concepto y la implementación del algoritmo kruskal. Al igual que otros algoritmos basados ​​en técnicas codiciosas, el algoritmo de Kruskal también se utiliza para encontrar el Árbol de expansión mínimo (MST) del gráfico. MST es el subconjunto de los bordes que conecta todos los vértices juntos sin formar ningún bucle o ciclos y con el peso mínimo posible

ALGORITMO KRUSKAL:

Inicialmente, este algoritmo encuentra un peso mínimo posible que conecta dos nodos cualesquiera en el gráfico.

1. Obtenga el número de vértices n, el peso de los vértices y las aristas.
2. Obtenga los pesos de los bordes y colóquelos en la cola de prioridad en orden ascendente.
3. Cree un conjunto disjunto donde cada vértice será un conjunto disjunto separado.
4. Encuentre el valor mínimo de la cola de prioridad y sus vértices de conexión.
5. Haga una unión de esos vértices y marque los bordes como aceptados si no forman un ciclo en el árbol de expansión mínimo y elimine el mínimo de la cola de prioridad.
6. Repite todos los pasos hasta que todos los vértices del árbol estén conectados.

PASOS PARA RESOLVER:

1. Enumere todos los bordes del gráfico dado. Anote el borde y el peso del nodo respectivo.
2. Ordene los bordes en orden ascendente según el peso del borde.
   

   

3. Elija el borde más pequeño y verifique si forma un ciclo con el MST formado.
4. Si este borde forma un ciclo, descarte este borde y vaya al siguiente borde; de ​​lo contrario, incluya este borde en el árbol de expansión mínimo formado hasta ahora.
5. El paso mencionado anteriormente se repite hasta que haya (N-1) bordes en el MST. N- no. de vértices.
   

   

Veamos cómo implementar este algoritmo de Kruskal en la programación Java. Si necesita implementar este algoritmo en cualquier otro lenguaje de programación, háganoslo saber en la sección de comentarios.

IMPLEMENTACIÓN JAVA DEL ALGORITMO KRUSKAL:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class kruskal
{
    class Edge implements Comparable<Edge>
    {
        int src, dest, weight;
        public int compareTo(Edge compareEdge)
        {
            return this.weight-compareEdge.weight;
        }
    };
    class subset
    {
        int parent, rank;
    };
 
    int V, E;    
    Edge edge[];
    kruskal(int v, int e)
    {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i=0; i<e; ++i)
            edge[i] = new Edge();
    }
    int find(subset subsets[], int i)
    {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
 
        return subsets[i].parent;
    }
    void Union(subset subsets[], int x, int y)
    {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else
        {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }
  // The main function to construct MST using Kruskal's algorithm
    void KruskalMST()
    {
        Edge result[] = new Edge[V];  
        int e = 0;  
        int i = 0; 
        for (i=0; i<V; ++i)
        Arrays.sort(edge);
        subset subsets[] = new subset[V];
        for(i=0; i<V; ++i)
            subsets[i]=new subset();
        for (int v = 0; v < V; ++v)
        {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
        i = 0; 
        while (e < V - 1)
        {
            Edge next_edge = new Edge();
            next_edge = edge[i++];
 
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);
            if (x != y)
            {
                result[e++] = next_edge;
                Union(subsets, x, y);
            }
           
        }
 
        System.out.println("Following are the edges in " + 
                                     "the constructed MST");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src+" -- " + 
                   result[i].dest+" == " + result[i].weight);
    }
 
    // Driver Program
    public static void main (String[] args)
    {
 
        /* Let us create following weighted graph
                 10
            0--------1
            |       |
           6|   5   |15
            |       |
            2--------3
                4       */
        int V = 4;  
        int E = 5;  
        kruskal graph = new kruskal(V, E);
 
        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;
 
        // add edge 0-2
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;
 
        // add edge 0-3
        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;
 
        // add edge 1-3
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;
 
        // add edge 2-3
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;
 
        graph.KruskalMST();
    }
}

El resultado de este programa será:

Espero que este artículo le ayude a comprender el algoritmo de Kruskal. Si está interesado en la programación, suscríbase a nuestro boletín por correo electrónico para recibir todos los tutoriales de programación. Además, consulte nuestros artículos sobre algoritmos de prim y Dijkstra.