Algoritmo de Kruskal: ¡explicado con un ejemplo!

algoritmo de kruskal
algoritmo de kruskal

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

Contenido

  • 1 ALGORITMO KRUSKAL:
        • 1.0.0.1 PASOS PARA RESOLVER:
    • 1.1 IMPLEMENTACIÓN JAVA DEL ALGORITMO KRUSKAL:
        • 1.1.0.1 El resultado de este programa será:

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:

algoritmo kruskal
Algoritmo de Kruskal
  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.
    algoritmo kruskal
    Algoritmo de Kruskal
  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.
    algoritmo kruskal
    Algoritmo de Kruskal

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á:

algoritmo kruskal
Algoritmo de Kruskal: salida de Java

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.

ARTÍCULOS RELACIONADOS:

Lenovo Vibe C2 con pantalla HD de 5 pulgadas y soporte 4G presentado

Lenovo Vibe C2 con pantalla HD de 5 pulgadas y soporte 4G presentado

Con Lenovo enfocándose en su cartera de teléfonos inteligentes económicos, la compañía ahora ha lanzado el Lenovo Vibe C2. Lenovo ...
Leer Más
Mercury mTAB Star M830G con llamadas de voz lanzadas para Rs.  6999

Mercury mTAB Star M830G con llamadas de voz lanzadas para Rs. 6999

Con la creciente demanda de tabletas Android asequibles, Mercury ha lanzado Mercury mTAB Star M830G a un precio muy bajo.Mercury ...
Leer Más
¿Es Xiaomi Redmi 5 Plus realmente el Redmi Note 5?

¿Es Xiaomi Redmi 5 Plus realmente el Redmi Note 5?

La marca china de teléfonos inteligentes Xiaomi lanzó el Redmi Note 4 en la India en enero de este año, ...
Leer Más
Misterioso teléfono Motorola certificado en Brasil;  Podría ser el sucesor de Moto G

Misterioso teléfono Motorola certificado en Brasil; Podría ser el sucesor de Moto G

Como era de esperar, el Moto G ha tenido un éxito sorprendente en la India y en todo el mundo ...
Leer Más
Lanzamiento de la serie Alcatel One Touch Pop con cuatro teléfonos inteligentes Android económicos

Lanzamiento de la serie Alcatel One Touch Pop con cuatro teléfonos inteligentes Android económicos

Alcatel parece ser la única empresa que se toma en serio la IFA 2013. La compañía, después de anunciar los ...
Leer Más
Moto G5 llegará a las costas indias el 4 de abril

Moto G5 llegará a las costas indias el 4 de abril

Después de lanzar el Moto G5 Plus en India hace unas dos semanas, Motorola ahora lanzará el Moto G5 en ...
Leer Más

Vota este artículo

0 / 5. 0