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:

Sony Xperia XZ2 Compact anunciado con pantalla FHD + HDR de 5 pulgadas, Snapdragon 845 SoC y cámara de 19 MP

Sony Xperia XZ2 Compact anunciado con pantalla FHD + HDR de 5 pulgadas, Snapdragon 845 SoC y cámara de 19 MP

El gigante tecnológico japonés Sony en el Mobile World Congress (MWC) 2018 anunció su teléfono inteligente Xperia XZ2. Con el ...
Leer Más
Se detallan los procesadores Samsung Galaxy S5 y Note 3 Neo Exynos

Se detallan los procesadores Samsung Galaxy S5 y Note 3 Neo Exynos

Samsung ha estado dando pistas durante mucho tiempo de que habrá una versión Samsung Galaxy S5 Exynos. Pero finalmente, ha ...
Leer Más
Xiaomi lanza Mi Pocket Speaker 2 en India con un diseño minimalista y una duración de batería de 7 horas

Xiaomi lanza Mi Pocket Speaker 2 en India con un diseño minimalista y una duración de batería de 7 horas

El año pasado, aproximadamente al mismo tiempo, la marca china de teléfonos inteligentes Xiaomi lanzó Mi Bluetooth Speaker Mini en ...
Leer Más
Cómo reiniciar un iPhone o iPad

Cómo reiniciar un iPhone o iPad

En este tutorial mostramos cómo reiniciar y reiniciar un iPhone o iPad. Esta puede ser una solución eficaz si su ...
Leer Más
WhatsApp para Android ahora te permite compartir cualquier tipo de archivo

WhatsApp para Android ahora te permite compartir cualquier tipo de archivo

Hace más de dos semanas, le dijimos que WhatsApp pronto podría permitirle compartir cualquier tipo de archivo que desee, ya ...
Leer Más
Cómo usar AirPlay

Cómo usar AirPlay

El iPhone es un poderoso dispositivo de mano que le permite ver, editar y reproducir muchos de los archivos que ...
Leer Más