En este artículo, discutiremos el algoritmo de Kruskal. Aquí también veremos la complejidad, funcionamiento, ejemplo e implementación del algoritmo de Kruskal.
Pero antes de pasar directamente al algoritmo, primero debemos comprender los términos básicos como árbol de expansión y árbol de expansión mínimo.
árbol de expansión - Un árbol de expansión es el subgrafo de un gráfico conexo no dirigido.
Árbol de expansión mínimo - El árbol de expansión mínimo se puede definir como el árbol de expansión en el que la suma de los pesos de los bordes es mínima. El peso del árbol de expansión es la suma de los pesos dados a los bordes del árbol de expansión.
Ahora, comencemos con el tema principal.
Algoritmo de Kruskal se utiliza para encontrar el árbol de expansión mínimo para un gráfico ponderado conectado. El objetivo principal del algoritmo es encontrar el subconjunto de aristas mediante las cuales podemos atravesar cada vértice del gráfico. Sigue el enfoque codicioso que encuentra una solución óptima en cada etapa en lugar de centrarse en un óptimo global.
¿Cómo funciona el algoritmo de Kruskal?
En el algoritmo de Kruskal, comenzamos desde los bordes con el peso más bajo y seguimos agregando bordes hasta alcanzar el objetivo. Los pasos para implementar el algoritmo de Kruskal se enumeran a continuación:
- Primero, ordene todos los bordes de bajo a alto.
- Ahora, tome el borde con el peso más bajo y agréguelo al árbol de expansión. Si el borde que se va a agregar crea un ciclo, rechace el borde.
- Continúe agregando los bordes hasta llegar a todos los vértices y se crea un árbol de expansión mínimo.
Las aplicaciones del algoritmo de Kruskal son:
- El algoritmo de Kruskal se puede utilizar para diseñar el cableado eléctrico entre ciudades.
- Se puede utilizar para establecer conexiones LAN.
Ejemplo del algoritmo de Kruskal
Ahora, veamos el funcionamiento del algoritmo de Kruskal usando un ejemplo. Será más fácil entender el algoritmo de Kruskal con un ejemplo.
Supongamos que un grafico ponderado es:
El peso de los bordes del gráfico anterior se proporciona en la siguiente tabla:
| Borde | AB | C.A. | ANUNCIO | PERO | antes de Cristo | CD | DE |
| Peso | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Ahora, ordene los bordes indicados anteriormente en orden ascendente de sus pesos.
| Borde | AB | DE | antes de Cristo | CD | PERO | C.A. | ANUNCIO |
| Peso | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Ahora comencemos a construir el árbol de expansión mínima.
patrón de diseño de fábrica
Paso 1 - Primero, agrega el borde. AB con peso 1 al MST.
Paso 2 - Agrega el borde DE con peso 2 al MST ya que no está creando el ciclo.
Paso 3 - Agrega el borde antes de Cristo con peso 3 al MST, ya que no está creando ningún ciclo o bucle.
Etapa 4 - Ahora, elige el borde CD con peso 4 al MST, ya que no está formando el ciclo.
Paso 5 - Después de eso, elige el borde. PERO con peso 5. Incluir este borde creará el ciclo, así que deséchalo.
Paso 6 - Elige el borde C.A. con peso 7. Incluir este borde creará el ciclo, así que deséchalo.
Paso 7 - Elige el borde ANUNCIO con peso 10. Incluir este borde también creará el ciclo, así que deséchalo.
Entonces, el árbol de expansión mínimo final obtenido del gráfico ponderado dado utilizando el algoritmo de Kruskal es:
El costo del MST es = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Ahora, el número de aristas en el árbol de arriba es igual al número de vértices menos 1. Entonces, el algoritmo se detiene aquí.
Algoritmo
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Complejidad del algoritmo de Kruskal
Ahora veamos la complejidad temporal del algoritmo de Kruskal.
La complejidad temporal del algoritmo de Kruskal es O (E logE) u O (V logV), donde E es el no. de aristas, y V es el no. de vértices.
Implementación del algoritmo de Kruskal.
Ahora veamos la implementación del algoritmo de Kruskal.
Programa: Escriba un programa para implementar el algoritmo de Kruskal en C++.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>