Árbol de expansión mínimo de Kruskal usando STL en C++

Dado un gráfico ponderado, conectado y no dirigido, encuentre el árbol generador mínimo ( MST ) del gráfico utilizando el algoritmo de Kruskal .

Input :   Graph as an array of edges
Output :  Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37

Note :  There are two possible MSTs, the other
        MST includes edge 1-2 in place of 0-7. 

Hemos discutido a continuación las implementaciones de MST de Kruskal. Algoritmos codiciosos | Conjunto 2 (algoritmo de árbol de expansión mínimo de Kruskal) A continuación se muestran los pasos para encontrar MST utilizando el algoritmo de Kruskal

  1. Ordene todos los bordes en orden no decreciente de su peso.
  2. Elija el borde más pequeño. Compruebe si forma un ciclo con el árbol de expansión formado hasta ahora. Si no se forma el ciclo, incluya este borde. De lo contrario, deséchalo.
  3. Repita el paso 2 hasta que haya aristas (V-1) en el árbol de expansión.

Aquí hay algunos puntos clave que nos serán útiles para implementar el algoritmo de Kruskal usando STL.

  1. Utilice un vector de aristas que conste de todas las aristas del gráfico y cada elemento de un vector contendrá 3 parámetros: fuente, destino y el costo de una arista entre la fuente y el destino.
vector<pair<int, pair<int, int> > > edges;
  1. Aquí, en el par externo (es decir, pair<int,pair<int,int> > ), el primer elemento corresponde al costo de una arista mientras que el segundo elemento es en sí mismo una pareja y contiene dos vértices de la arista.
  2. Use el std::sort incorporado para ordenar los bordes en orden no decreciente; por defecto, la función de clasificación ordena en orden no decreciente.
  3. Usamos el algoritmo de búsqueda de unión para verificar si el borde actual forma un ciclo si se agrega en el MST actual. En caso afirmativo, deséchelo, de lo contrario, inclúyalo (unión).

Pseudocódigo: 

// Initialize result
mst_weight = 0

// Create V single item sets
for each vertex v
    parent[v] = v;
    rank[v] = 0;

Sort all edges into non decreasing 
order by weight w

for each (u, v) taken from the sorted list  E
    do if FIND-SET(u) != FIND-SET(v)
        print edge(u, v)
        mst_weight += weight of edge(u, v)
        UNION(u, v)

A continuación se muestra la implementación en C++ del algoritmo anterior. 

C++

// C++ program for Kruskal's algorithm to find Minimum
// Spanning Tree of a given connected, undirected and
// weighted graph
#include<bits/stdc++.h>
using namespace std;
  
// Creating shortcut for an integer pair
typedef pair<int, int> iPair;
  
// Structure to represent a graph
struct Graph
{
    int V, E;
    vector< pair<int, iPair> > edges;
  
    // Constructor
    Graph(int V, int E)
    {
        this->V = V;
        this->E = E;
    }
  
    // Utility function to add an edge
    void addEdge(int u, int v, int w)
    {
        edges.push_back({w, {u, v}});
    }
  
    // Function to find MST using Kruskal's
    // MST algorithm
    int kruskalMST();
};
  
// To represent Disjoint Sets
struct DisjointSets
{
    int *parent, *rnk;
    int n;
  
    // Constructor.
    DisjointSets(int n)
    {
        // Allocate memory
        this->n = n;
        parent = new int[n+1];
        rnk = new int[n+1];
  
        // Initially, all vertices are in
        // different sets and have rank 0.
        for (int i = 0; i <= n; i++)
        {
            rnk[i] = 0;
  
            //every element is parent of itself
            parent[i] = i;
        }
    }
  
    // Find the parent of a node 'u'
    // Path Compression
    int find(int u)
    {
        /* Make the parent of the nodes in the path
        from u--> parent[u] point to parent[u] */
        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
  
    // Union by rank
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
  
        /* Make tree with smaller height
        a subtree of the other tree */
        if (rnk[x] > rnk[y])
            parent[y] = x;
        else // If rnk[x] <= rnk[y]
            parent[x] = y;
  
        if (rnk[x] == rnk[y])
            rnk[y]++;
    }
};
  
/* Functions returns weight of the MST*/
  
int Graph::kruskalMST()
{
    int mst_wt = 0; // Initialize result
  
    // Sort edges in increasing order on basis of cost
    sort(edges.begin(), edges.end());
  
    // Create disjoint sets
    DisjointSets ds(V);
  
    // Iterate through all sorted edges
    vector< pair<int, iPair> >::iterator it;
    for (it=edges.begin(); it!=edges.end(); it++)
    {
        int u = it->second.first;
        int v = it->second.second;
  
        int set_u = ds.find(u);
        int set_v = ds.find(v);
  
        // Check if the selected edge is creating
        // a cycle or not (Cycle is created if u
        // and v belong to same set)
        if (set_u != set_v)
        {
            // Current edge will be in the MST
            // so print it
            cout << u << " - " << v << endl;
  
            // Update MST weight
            mst_wt += it->first;
  
            // Merge two sets
            ds.merge(set_u, set_v);
        }
    }
  
    return mst_wt;
}
  
// Driver program to test above functions
int main()
{
    /* Let us create above shown weighted
    and undirected graph */
    int V = 9, E = 14;
    Graph g(V, E);
  
    // making above shown graph
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
  
    cout << "Edges of MST are \n";
    int mst_wt = g.kruskalMST();
  
    cout << "\nWeight of MST is " << mst_wt;
  
    return 0;
}
Producción

Edges of MST are 
6 - 7
2 - 8
5 - 6
0 - 1
2 - 5
2 - 3
0 - 7
3 - 4

Weight of MST is 37

Optimización: el código anterior se puede optimizar para detener el bucle principal de Kruskal cuando el número de bordes seleccionados se convierte en V-1. Sabemos que MST tiene bordes V-1 y no tiene sentido iterar después de seleccionar los bordes V-1. No hemos agregado esta optimización para mantener el código simple. 

La complejidad del tiempo y la ilustración paso a paso se analizan en una publicación anterior sobre el algoritmo de Kruskal. 

Este artículo es una contribución de Chirag Agrawal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *