Un árbol de expansión mínimo (MST) o árbol de expansión de peso mínimo para un gráfico ponderado, conectado y no dirigido es un árbol de expansión con un peso menor o igual al peso de todos los demás árboles de expansión. Para obtener más información sobre el árbol de expansión mínima, consulte Este artículo .
Introducción al algoritmo de Kruskal:
Aquí discutiremos El algoritmo de Kruskal para encontrar el MST de un gráfico ponderado dado.
En el algoritmo de Kruskal, ordene todos los bordes del gráfico dado en orden creciente. Luego continúa agregando nuevos bordes y nodos en el MST si el borde recién agregado no forma un ciclo. Selecciona el borde con peso mínimo al principio y el borde con peso máximo al final. Por tanto, podemos decir que realiza una elección localmente óptima en cada paso para encontrar la solución óptima. Por lo tanto este es un A continuación se detallan los pasos para encontrar MST usando el algoritmo de Kruskal:
- Ordena todos los bordes en orden no decreciente de su peso.
- Elige el borde más pequeño. Compruebe si forma un ciclo con el árbol de expansión formado hasta el momento. Si el ciclo no se forma, incluya este borde. De lo contrario, deséchelo.
- Repita el paso 2 hasta que haya bordes (V-1) en el árbol de expansión.
Paso 2 utiliza el Algoritmo de búsqueda de unión para detectar ciclos.
Por lo que recomendamos leer el siguiente post como requisito previo.
- Algoritmo de búsqueda de unión | Conjunto 1 (Detectar ciclo en un gráfico)
- Algoritmo de búsqueda de unión | Conjunto 2 (Unión por rango y compresión de ruta)
El algoritmo de Kruskal para encontrar el árbol de expansión de costo mínimo utiliza el enfoque codicioso. La elección codiciosa es elegir el borde de peso más pequeño que no provoque un ciclo en el MST construido hasta ahora. Entendámoslo con un ejemplo:
Ilustración:
A continuación se muestra la ilustración del enfoque anterior:
Gráfico de entrada:
El gráfico contiene 9 vértices y 14 aristas. Entonces, el árbol de expansión mínimo formado tendrá (9 – 1) = 8 aristas.
Después de clasificar:
Peso Fuente Destino 1 7 6 2 8 2 2 6 5 4 0 1 4 2 5 6 8 6 7 2 3 7 7 8 8 0 7 8 1 2 9 3 4 10 5 4 11 1 7 14 3 5 Ahora elija todos los bordes uno por uno de la lista ordenada de bordes.
Paso 1: Elija el borde 7-6. No se forma ningún ciclo, inclúyelo.
Agregue el borde 7-6 en el MST
Paso 2: Elija el borde 8-2. No se forma ningún ciclo, inclúyelo.
Agregue el borde 8-2 en el MST
java concatenando cadenasPaso 3: Elija el borde 6-5. No se forma ningún ciclo, inclúyelo.
Agregue el borde 6-5 en el MST
Etapa 4: Elija la ventaja 0-1. No se forma ningún ciclo, inclúyelo.
Agregue el borde 0-1 en el MST
Paso 5: Elija el borde 2-5. No se forma ningún ciclo, inclúyelo.
Agregue el borde 2-5 en el MST
Paso 6: Elija el borde 8-6. Dado que incluir esta arista da como resultado el ciclo, deséchela. Elija el borde 2-3: No se forma ningún ciclo, inclúyelo.
Agregue el borde 2-3 en el MST
Paso 7: Elija el borde 7-8. Dado que incluir esta arista da como resultado el ciclo, deséchela. Elija el borde 0-7. No se forma ningún ciclo, inclúyelo.
Agregue el borde 0-7 en MST
Paso 8: Elija el borde 1-2. Dado que incluir esta arista da como resultado el ciclo, deséchela. Elija el borde 3-4. No se forma ningún ciclo, inclúyelo.
Agregue el borde 3-4 en el MST
Nota: Dado que el número de aristas incluidas en el MST es igual a (V – 1), el algoritmo se detiene aquí
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach> > #include> using> namespace> std;> > // DSU data structure> // path compression + rank by union> class> DSU {> >int>* parent;> >int>* rank;> > public>:> >DSU(>int> n)> >{> >parent =>new> int>[n];> >rank =>new> int>[n];> > >for> (>int> i = 0; i parent[i] = -1; rank[i] = 1; } } // Find function int find(int i) { if (parent[i] == -1) return i; return parent[i] = find(parent[i]); } // Union function void unite(int x, int y) { int s1 = find(x); int s2 = find(y); if (s1 != s2) { if (rank[s1] parent[s1] = s2; } else if (rank[s1]>rango[s2]) { padre[s2] = s1; } más { padre[s2] = s1; rango[s1] += 1; } } } }; clase Gráfico { vectorint>> lista de bordes; En televisión; público: Gráfico(int V) { this->V = V; } // Función para agregar borde en un gráfico void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Ordenar todos los bordes sort(edgelist.begin(), edgelist.end()); // Inicializa el DSU DSU s(V); int respuesta = 0; corte<< 'Following are the edges in the ' 'constructed MST' << endl; for (auto edge : edgelist) { int w = edge[0]; int x = edge[1]; int y = edge[2]; // Take this edge in MST if it does // not forms a cycle if (s.find(x) != s.find(y)) { s.unite(x, y); ans += w; cout << x << ' -- ' << y << ' == ' << w << endl; } } cout << 'Minimum Cost Spanning Tree: ' << ans; } }; // Driver code int main() { Graph g(4); g.addEdge(0, 1, 10); g.addEdge(1, 3, 15); g.addEdge(2, 3, 4); g.addEdge(2, 0, 6); g.addEdge(0, 3, 5); // Function call g.kruskals_mst(); return 0; }> |
>
>
C
// C code to implement Kruskal's algorithm> > #include> #include> > // Comparator function to use in sorting> int> comparator(>const> void>* p1,>const> void>* p2)> {> >const> int>(*x)[3] = p1;> >const> int>(*y)[3] = p2;> > >return> (*x)[2] - (*y)[2];> }> > // Initialization of parent[] and rank[] arrays> void> makeSet(>int> parent[],>int> rank[],>int> n)> {> >for> (>int> i = 0; i parent[i] = i; rank[i] = 0; } } // Function to find the parent of a node int findParent(int parent[], int component) { if (parent[component] == component) return component; return parent[component] = findParent(parent, parent[component]); } // Function to unite two sets void unionSet(int u, int v, int parent[], int rank[], int n) { // Finding the parents u = findParent(parent, u); v = findParent(parent, v); if (rank[u] parent[u] = v; } else if (rank[u]>rango[v]) { padre[v] = u; } más { padre[v] = u; // Dado que el rango aumenta si // los rangos de dos conjuntos son el mismo rango[u]++; } } // Función para encontrar el MST void kruskalAlgo(int n, int edge[n][3]) { // Primero ordenamos la matriz de bordes en orden ascendente // para que podamos acceder a distancias mínimas/costo qsort(edge , n, tamaño de (borde [0]), comparador); int padre[n]; rango int[n]; // Función para inicializar padre[] y rango[] makeSet(padre, rango, n); // Para almacenar el coste mínimo int minCost = 0; printf( 'A continuación se muestran los bordes en el MST construido
'); for (int i = 0; i int v1 = findParent(padre, borde[i][0]); int v2 = findParent(padre, borde[i][1]); int wt = borde[i][2] ; // Si los padres son diferentes, // significa que están en conjuntos diferentes, así que // únelos if (v1 != v2) { unionSet(v1, v2, parent, ranking, n); '%d -- %d == %d
', edge[i][0], edge[i][1], wt } } printf('Árbol de expansión de costo mínimo: %d); n', minCost); // Código del controlador int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } }; kruskalAlgo(5, borde 0); |
>
// Java program for Kruskal's algorithm>>import>java.util.ArrayList;>import>java.util.Comparator;>import>java.util.List;>>public>class>KruskalsMST {>>>// Defines edge structure>>static>class>Edge {>>int>src, dest, weight;>>>public>Edge(>int>src,>int>dest,>int>weight)>>{>>this>.src = src;>>this>.dest = dest;>>this>.weight = weight;>>}>>}>>>// Defines subset element structure>>static>class>Subset {>>int>parent, rank;>>>public>Subset(>int>parent,>int>rank)>>{>>this>.parent = parent;>>this>.rank = rank;>>}>>}>>>// Starting point of program execution>>public>static>void>main(String[] args)>>{>>int>V =>4>;>>List graphEdges =>new>ArrayList(>>List.of(>new>Edge(>0>,>1>,>10>),>new>Edge(>0>,>2>,>6>),>>new>Edge(>0>,>3>,>5>),>new>Edge(>1>,>3>,>15>),>>new>Edge(>2>,>3>,>4>)));>>>// Sort the edges in non-decreasing order>>// (increasing with repetition allowed)>>graphEdges.sort(>new>Comparator() {>>@Override>public>int>compare(Edge o1, Edge o2)>>{>>return>o1.weight - o2.weight;>>}>>});>>>kruskals(V, graphEdges);>>}>>>// Function to find the MST>>private>static>void>kruskals(>int>V, List edges)>>{>>int>j =>0>;>>int>noOfEdges =>0>;>>>// Allocate memory for creating V subsets>>Subset subsets[] =>new>Subset[V];>>>// Allocate memory for results>>Edge results[] =>new>Edge[V];>>>// Create V subsets with single elements>>for>(>int>i =>0>; i subsets[i] = new Subset(i, 0); } // Number of edges to be taken is equal to V-1 while (noOfEdges 1) { // Pick the smallest edge. And increment // the index for next iteration Edge nextEdge = edges.get(j); int x = findRoot(subsets, nextEdge.src); int y = findRoot(subsets, nextEdge.dest); // If including this edge doesn't cause cycle, // include it in result and increment the index // of result for next edge if (x != y) { results[noOfEdges] = nextEdge; union(subsets, x, y); noOfEdges++; } j++; } // Print the contents of result[] to display the // built MST System.out.println( 'Following are the edges of the constructed MST:'); int minCost = 0; for (int i = 0; i System.out.println(results[i].src + ' -- ' + results[i].dest + ' == ' + results[i].weight); minCost += results[i].weight; } System.out.println('Total cost of MST: ' + minCost); } // Function to unite two disjoint sets private static void union(Subset[] subsets, int x, int y) { int rootX = findRoot(subsets, x); int rootY = findRoot(subsets, y); if (subsets[rootY].rank subsets[rootY].parent = rootX; } else if (subsets[rootX].rank subsets[rootX].parent = rootY; } else { subsets[rootY].parent = rootX; subsets[rootX].rank++; } } // Function to find parent of a set private static int findRoot(Subset[] subsets, int i) { if (subsets[i].parent == i) return subsets[i].parent; subsets[i].parent = findRoot(subsets, subsets[i].parent); return subsets[i].parent; } } // This code is contributed by Salvino D'sa>>>Python3
# Python program for Kruskal's algorithm to find># Minimum Spanning Tree of a given connected,># undirected and weighted graph>>># Class to represent a graph>class>Graph:>>>def>__init__(>self>, vertices):>>self>.V>=>vertices>>self>.graph>=>[]>>># Function to add an edge to graph>>def>addEdge(>self>, u, v, w):>>self>.graph.append([u, v, w])>>># A utility function to find set of an element i>># (truly uses path compression technique)>>def>find(>self>, parent, i):>>if>parent[i] !>=>i:>>># Reassignment of node's parent>># to root node as>># path compression requires>>parent[i]>=>self>.find(parent, parent[i])>>return>parent[i]>>># A function that does union of two sets of x and y>># (uses union by rank)>>def>union(>self>, parent, rank, x, y):>>># Attach smaller rank tree under root of>># high rank tree (Union by Rank)>>if>rank[x] parent[x] = y elif rank[x]>rango[y]: padre[y] = x # Si los rangos son iguales, entonces haga uno como raíz # e incremente su rango en uno más: padre[y] = x rango[x] += 1 # La función principal a construir MST # usando el algoritmo de Kruskal def KruskalMST(self): # Esto almacenará el resultado MST resultante = [] # Una variable de índice, utilizada para bordes ordenados i = 0 # Una variable de índice, utilizada para resultado[] e = 0 # Ordena todos los bordes en # orden no decreciente de su # peso self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rango = [] # Crea subconjuntos V con elementos individuales para el nodo en el rango (self.V): parent.append (nodo) rango.append (0) # El número de aristas que se tomarán es menor que V-1 mientras que e>>C#
fusionar ordenar java
// C# Code for the above approach>>using>System;>>class>Graph {>>>// A class to represent a graph edge>>class>Edge : IComparable {>>public>int>src, dest, weight;>>>// Comparator function used for sorting edges>>// based on their weight>>public>int>CompareTo(Edge compareEdge)>>{>>return>this>.weight - compareEdge.weight;>>}>>}>>>// A class to represent>>// a subset for union-find>>public>class>subset {>>public>int>parent, rank;>>};>>>// V->No. de vértices & E->nº de aristas>>int>V, E;>>>// Collection of all edges>>Edge[] edge;>>>// Creates a graph with V vertices and E edges>>Graph(>int>v,>int>e)>>{>>V = v;>>E = e;>>edge =>new>Edge[E];>>for>(>int>i = 0; i edge[i] = new Edge(); } // A utility function to find set of an element i // (uses path compression technique) int find(subset[] subsets, int i) { // Find root and make root as // parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } // A function that does union of // two sets of x and y (uses union by rank) void Union(subset[] subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); // Attach smaller rank tree under root of // high rank tree (Union by Rank) if (subsets[xroot].rank subsets[xroot].parent = yroot; else if (subsets[xroot].rank>subconjuntos[yroot].rank) subconjuntos[yroot].parent = xroot; // Si los rangos son iguales, entonces crea uno como raíz // e incrementa su rango en uno más { subsets[yroot].parent = xroot; subconjuntos[xroot].rank++; } } // La función principal para construir MST // usando el algoritmo de Kruskal void KruskalMST() { // Esto almacenará el // MST resultante Edge[] resultado = new Edge[V]; // Una variable de índice, utilizada para resultado[] int e = 0; // Una variable de índice, utilizada para bordes ordenados int i = 0; for (i = 0; i result[i] = new Edge(); // Ordena todos los bordes en // orden no decreciente de su peso. Si no se nos permite // cambiar el gráfico dado, podemos crear // una copia de la matriz de bordes Array.Sort(edge); // Asigna memoria para crear V subconjuntos subset[] subsets = new subset[V] for (i = 0; i subsets[i] = new subset(); ; // Crea V subconjuntos con elementos individuales para (int v = 0; v subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // El número de aristas a tomar es igual a V-1 while (e // Escoge el borde más pequeño. E incrementa // el índice para la siguiente iteración Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // Si incluir este borde no causa el ciclo, // inclúyelo en el resultado e incrementa el índice // del resultado para el siguiente borde if (x != y) { resultado[e++] = next_edge; Union(subsets, x, y); // Imprime el contenido de resultado[] para mostrar // el MST Console.WriteLine('A continuación se muestran los bordes en ' + ' el MST construido'); int costo mínimo = 0; for (i = 0; i Console.WriteLine(resultado[i].src + ' -- ' + resultado[i].dest + ' == ' + resultado[i].peso); costo mínimo += resultado[i].weight; } Console.WriteLine('Árbol de expansión de costo mínimo: ' + costo mínimo Console.ReadLine() } // Código del controlador public static void Main(String[] args) { int V = 4; int E = 5; Gráfico gráfico = nuevo Gráfico(V, E); // agregar borde 0-1 gráfico.borde[0].src = 0; gráfico.borde[0].dest = 1; Graph.edge[0].weight = 10; // agrega el borde 0-2 Graph.edge[1].src = 0; Graph.edge[1].dest = 2; ; // agrega el gráfico del borde 0-3. borde[3].src = 1; gráfico.borde[3].dest = 3; gráfico.borde[3].peso = 15; // agregar borde 2-3 gráfico.borde[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4; // Llamada a función graph.KruskalMST() } } // Este código es una contribución de Aakash Hasija>'>;>
>// JavaScript implementation of the krushkal's algorithm.>>function>makeSet(parent,rank,n)>{>>for>(let i=0;i { parent[i]=i; rank[i]=0; } } function findParent(parent,component) { if(parent[component]==component) return component; return parent[component] = findParent(parent,parent[component]); } function unionSet(u, v, parent, rank,n) { //this function unions two set on the basis of rank //as shown below u=findParent(parent,u); v=findParent(parent,v); if(rank[u] { parent[u]=v; } else if(rank[u] { parent[v]=u; } else { parent[v]=u; rank[u]++;//since the rank increases if the ranks of two sets are same } } function kruskalAlgo(n, edge) { //First we sort the edge array in ascending order //so that we can access minimum distances/cost edge.sort((a, b)=>{ devolver a[2] - b[2]; }) //La función de clasificación rápida incorporada viene con stdlib.h //vaya a https://www.techcodeview.com La clasificación de bordes lleva O(E * logE) tiempo. Después de ordenar, iteramos por todos los bordes y aplicamos el algoritmo de búsqueda y unión. Las operaciones de búsqueda y unión pueden tardar como máximo un tiempo O(logV). Entonces, la complejidad general es O (E * logE + E * logV) tiempo. El valor de E puede ser como máximo O(V2), por lo que O(logV) y O(logE) son iguales. Por lo tanto, la complejidad del tiempo general es O (E * logE) u O (E * logV) Espacio auxiliar: O (V + E), donde V es el número de vértices y E es el número de aristas en el gráfico. Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de techcodeview.com.>