A continuación se muestran los pasos para encontrar MST usando el algoritmo de Kruskal
1. Clasifique 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 n.º 2 hasta que haya aristas (V-1) en el árbol de expansión.
Hemos discutido una implementación del algoritmo de Kruskal en una publicación anterior . En esta publicación, se analiza una implementación más simple para la array de adyacencia.
C++
// Simple C++ implementation for Kruskal's
// algorithm
#include <bits/stdc++.h>
using namespace std;
#define V 5
int parent[V];
// Find set of vertex i
int find(int i)
{
while (parent[i] != i)
i = parent[i];
return i;
}
// Does union of i and j. It returns
// false if i and j are already in same
// set.
void union1(int i, int j)
{
int a = find(i);
int b = find(j);
parent[a] = b;
}
// Finds MST using Kruskal's algorithm
void kruskalMST(int cost[][V])
{
int mincost = 0; // Cost of min MST.
// Initialize sets of disjoint sets.
for (int i = 0; i < V; i++)
parent[i] = i;
// Include minimum weight edges one by one
int edge_count = 0;
while (edge_count < V - 1) {
int min = INT_MAX, a = -1, b = -1;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (find(i) != find(j) && cost[i][j] < min) {
min = cost[i][j];
a = i;
b = j;
}
}
}
union1(a, b);
printf("Edge %d:(%d, %d) cost:%d \n",
edge_count++, a, b, min);
mincost += min;
}
printf("\n Minimum cost= %d \n", mincost);
}
// driver program to test above function
int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int cost[][V] = {
{ INT_MAX, 2, INT_MAX, 6, INT_MAX },
{ 2, INT_MAX, 3, 8, 5 },
{ INT_MAX, 3, INT_MAX, INT_MAX, 7 },
{ 6, 8, INT_MAX, INT_MAX, 9 },
{ INT_MAX, 5, 7, 9, INT_MAX },
};
// Print the solution
kruskalMST(cost);
return 0;
}
Java
// Simple Java implementation for Kruskal's
// algorithm
import java.util.*;
class GFG
{
static int V = 5;
static int[] parent = new int[V];
static int INF = Integer.MAX_VALUE;
// Find set of vertex i
static int find(int i)
{
while (parent[i] != i)
i = parent[i];
return i;
}
// Does union of i and j. It returns
// false if i and j are already in same
// set.
static void union1(int i, int j)
{
int a = find(i);
int b = find(j);
parent[a] = b;
}
// Finds MST using Kruskal's algorithm
static void kruskalMST(int cost[][])
{
int mincost = 0; // Cost of min MST.
// Initialize sets of disjoint sets.
for (int i = 0; i < V; i++)
parent[i] = i;
// Include minimum weight edges one by one
int edge_count = 0;
while (edge_count < V - 1)
{
int min = INF, a = -1, b = -1;
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (find(i) != find(j) && cost[i][j] < min)
{
min = cost[i][j];
a = i;
b = j;
}
}
}
union1(a, b);
System.out.printf("Edge %d:(%d, %d) cost:%d \n",
edge_count++, a, b, min);
mincost += min;
}
System.out.printf("\n Minimum cost= %d \n", mincost);
}
// Driver code
public static void main(String[] args)
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int cost[][] = {
{ INF, 2, INF, 6, INF },
{ 2, INF, 3, 8, 5 },
{ INF, 3, INF, INF, 7 },
{ 6, 8, INF, INF, 9 },
{ INF, 5, 7, 9, INF },
};
// Print the solution
kruskalMST(cost);
}
}
// This code contributed by Rajput-Ji
Python3
# Python implementation for Kruskal's
# algorithm
# Find set of vertex i
def find(i):
while parent[i] != i:
i = parent[i]
return i
# Does union of i and j. It returns
# false if i and j are already in same
# set.
def union(i, j):
a = find(i)
b = find(j)
parent[a] = b
# Finds MST using Kruskal's algorithm
def kruskalMST(cost):
mincost = 0 # Cost of min MST
# Initialize sets of disjoint sets
for i in range(V):
parent[i] = i
# Include minimum weight edges one by one
edge_count = 0
while edge_count < V - 1:
min = INF
a = -1
b = -1
for i in range(V):
for j in range(V):
if find(i) != find(j) and cost[i][j] < min:
min = cost[i][j]
a = i
b = j
union(a, b)
print('Edge {}:({}, {}) cost:{}'.format(edge_count, a, b, min))
edge_count += 1
mincost += min
print("Minimum cost= {}".format(mincost))
# Driver code
# Let us create the following graph
# 2 3
# (0)--(1)--(2)
# | / \ |
# 6| 8/ \5 |7
# | / \ |
# (3)-------(4)
# 9
V = 5
parent = [i for i in range(V)]
INF = float('inf')
cost = [[INF, 2, INF, 6, INF],
[2, INF, 3, 8, 5],
[INF, 3, INF, INF, 7],
[6, 8, INF, INF, 9],
[INF, 5, 7, 9, INF]]
# Print the solution
kruskalMST(cost)
# This code is contributed by ng24_7
C#
// Simple C# implementation for Kruskal's
// algorithm
using System;
class GFG
{
static int V = 5;
static int[] parent = new int[V];
static int INF = int.MaxValue;
// Find set of vertex i
static int find(int i)
{
while (parent[i] != i)
i = parent[i];
return i;
}
// Does union of i and j. It returns
// false if i and j are already in same
// set.
static void union1(int i, int j)
{
int a = find(i);
int b = find(j);
parent[a] = b;
}
// Finds MST using Kruskal's algorithm
static void kruskalMST(int [,]cost)
{
int mincost = 0; // Cost of min MST.
// Initialize sets of disjoint sets.
for (int i = 0; i < V; i++)
parent[i] = i;
// Include minimum weight edges one by one
int edge_count = 0;
while (edge_count < V - 1)
{
int min = INF, a = -1, b = -1;
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (find(i) != find(j) && cost[i, j] < min)
{
min = cost[i, j];
a = i;
b = j;
}
}
}
union1(a, b);
Console.Write("Edge {0}:({1}, {2}) cost:{3} \n",
edge_count++, a, b, min);
mincost += min;
}
Console.Write("\n Minimum cost= {0} \n", mincost);
}
// Driver code
public static void Main(String[] args)
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int [,]cost = {
{ INF, 2, INF, 6, INF },
{ 2, INF, 3, 8, 5 },
{ INF, 3, INF, INF, 7 },
{ 6, 8, INF, INF, 9 },
{ INF, 5, 7, 9, INF },
};
// Print the solution
kruskalMST(cost);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Simple Javascript implementation for Kruskal's
// algorithm
var V = 5;
var parent = Array(V).fill(0);
var INF = 1000000000;
// Find set of vertex i
function find(i)
{
while (parent[i] != i)
i = parent[i];
return i;
}
// Does union of i and j. It returns
// false if i and j are already in same
// set.
function union1(i, j)
{
var a = find(i);
var b = find(j);
parent[a] = b;
}
// Finds MST using Kruskal's algorithm
function kruskalMST(cost)
{
var mincost = 0; // Cost of min MST.
// Initialize sets of disjoint sets.
for (var i = 0; i < V; i++)
parent[i] = i;
// Include minimum weight edges one by one
var edge_count = 0;
while (edge_count < V - 1)
{
var min = INF, a = -1, b = -1;
for (var i = 0; i < V; i++)
{
for (var j = 0; j < V; j++)
{
if (find(i) != find(j) && cost[i][j] < min)
{
min = cost[i][j];
a = i;
b = j;
}
}
}
union1(a, b);
document.write(`Edge ${edge_count++}:(${a},
${b}) cost:${min} <br>`);
mincost += min;
}
document.write(`<br> Minimum cost= ${mincost} <br>`);
}
// Driver code
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
var cost = [
[INF, 2, INF, 6, INF],
[2, INF, 3, 8, 5],
[INF, 3, INF, INF, 7],
[6, 8, INF, INF, 9],
[INF, 5, 7, 9, INF]];
// Print the solution
kruskalMST(cost);
</script>
Producción:
Edge 0:(0, 1) cost:2 Edge 1:(1, 2) cost:3 Edge 2:(1, 4) cost:5 Edge 3:(0, 3) cost:6 Minimum cost= 16
Tenga en cuenta que la solución anterior no es eficiente. La idea es proporcionar una implementación simple para representaciones de array de adyacencia. Consulte a continuación las implementaciones eficientes.
Algoritmo de árbol de expansión mínimo de Kruskal | Árbol de expansión mínimo de Greedy Algo-2 Kruskal usando STL en C++
Publicación traducida automáticamente
Artículo escrito por AnkurKarmakar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA