Algoritmo de Kruskal

Árbol mínimo

Un gráfico que no tiene direcciones se llama gráfico no dirigido. Cada gráfico debe tener una ruta de un nodo a otro nodo. Un árbol de expansión también es un gráfico conectado no dirigido donde todos los nodos del gráfico están presentes con bordes mínimos. Si un árbol de expansión no tiene todos los nodos del gráfico, entonces no podemos decir que es un árbol de expansión. Los pesos totales del árbol de expansión serán menores que el peso original del gráfico a medida que lo conectamos a través de los bordes de peso mínimo. El árbol de expansión tampoco tiene un ciclo. Cualquier gráfico tiene más de un árbol de expansión, pero solo uno de ellos será único. Lo llamamos un árbol de expansión mínimo ya que estamos intentando crear un gráfico completo con todos los nodos mientras mantenemos el peso bajo.

Entendamos el árbol de expansión mínimo con un ejemplo. Entonces, como sabemos, el árbol de expansión mínimo es parte del gráfico pero con menos costo. Entonces, este escenario se puede ilustrar con un ejemplo. Supongamos que tenemos un gráfico como este.

El gráfico anterior se puede organizar de diferentes maneras para que se elimine el ciclo del gráfico, o de lo contrario no será un MST (árbol de expansión mínimo). Por lo tanto, eliminaremos el ciclo del gráfico y contaremos el costo total del gráfico. Tenemos cuatro nodos, o vértices (A, B, C y D).

Caso 1:

Después de eliminar el ciclo del gráfico, el costo del gráfico MST (mínimo de expansión mínimo) anterior es 56.

Caso -2:

Después de eliminar el ciclo del gráfico, el costo del gráfico MST (mínimo de expansión mínimo) anterior es 53.

Caso - 3:

Después de eliminar el ciclo del gráfico, el costo del gráfico MST (mínimo de expansión mínimo) anterior es 41.

Podemos ver que el último gráfico del costo total de Case-3 es mucho más bajo en comparación con los otros dos gráficos. Entonces, este gráfico es nuestro MST final (árbol de expansión mínimo) para el gráfico original. El motivo de los algoritmos de primeros o Kruskal es encontrar el costo del gráfico lo más bajo posible. Entonces ese es nuestro motivo en este artículo para explicar este MST.

Podemos dibujar un árbol de expansión con la ayuda de los siguientes dos métodos:

1. Algoritmo de Kruskal
2. Algoritmo de Prim

En este artículo, vamos a discutir el algoritmo de Kruskal. El algoritmo de Prim se discutirá en el próximo artículo.

Algoritmo de Kruskal

El algoritmo de Kruskal es muy fácil de implementar en comparación con el algoritmo de Prim porque no tenemos que preocuparnos por los vértices de adyacencia en este algoritmo. En este algoritmo, el algoritmo de Kruskal comienza desde todos los vértices del gráfico. Elegimos la vértice de borde de peso mínimo y comenzamos a crear el árbol de expansión mínimo. Elegimos otro borde con el peso mínimo y lo agregamos al árbol mínimo de expansión. Este proceso continúa hasta que no agregamos todos los nodos gráficos originales. Una vez que todos los nodos en el gráfico se agregan al árbol de expansión mínimo, el algoritmo se detendrá. Durante la creación del árbol de expansión mínimo de un gráfico, también tenemos que cuidar ese gráfico, no crear ningún ciclo porque los ciclos no deben estar en el árbol de expansión mínimo.

Entonces, si algún nodo crea el ciclo en el árbol de expansión mínimo, elegimos el otro nodo, incluso si el peso de este nodo es mayor que el nodo anterior que crea el ciclo.

El algoritmo de Kruskal es diferente del algoritmo de Prim. El algoritmo de Prim, mientras crea un árbol de expansión mínimo, comienza desde cualquier nodo o vértice y luego agrega otro nodo o vértice solo desde los nodos de adyacencia. Pero el algoritmo de Kruskal no le importa el nodo de adyacencia y siempre selecciona ese nodo que tiene menos peso, pero ese nodo no debe crear un ciclo en el árbol de expansión mínimo.

Pasos de algoritmo de Kruskal:

Se toman los siguientes pasos al escribir el código C ++ para el algoritmo de Kruskal.

1. Creamos una matriz para almacenar grupos de nodos o vértices del gráfico.
2. Creamos otra matriz para almacenar pesas de bordes de gráficos.
3. Para el árbol de expansión, creamos una nueva matriz.
4. Organizamos la matriz de bordes en orden ascendente.
5. Repetimos el paso 6 hasta que la matriz de pesas de borde ordenado no esté vacía.
6. Comparamos los dos grupos uno al lado del otro. En este caso, si un nodo de un grupo no coincide con el otro nodo, agregamos ese borde al árbol de expansión y lo agregamos al mismo grupo.
7. Iterar a través de todos los bordes del árbol de expansión para determinar su peso total.

Ahora, implementaremos los pasos de algoritmo anteriores utilizando un ejemplo. Tenemos el siguiente gráfico, y descubriremos el árbol de expansión mínimo para este gráfico.

Entonces, según el algoritmo, primero elegimos el borde de peso más pequeño, que es AB. Entonces elegimos ese borde y lo mantuvimos en la matriz de árboles de expansión. El peso del borde ab.

Ahora, elegimos el siguiente borde de peso más pequeño, CD, y mantenemos ese borde en la matriz de árboles mínimo de expansión. El peso del borde del CD es 12.

El siguiente borde más pequeño que obtuvimos fue BC, que guardamos en la matriz. El borde de BC ponderado es de 17.

Nuestro algoritmo se detendrá aquí porque tenemos todos los vértices de un gráfico, y tenemos nuestro árbol de expansión mínimo. El peso total de este MST es 9 + 12 + 17 = 38.

Programa: El siguiente es un código C ++ para el algoritmo de Kruskal.

#incluir
#incluir
#incluir
clase EdgeGraph
público:
int nodestart;
int nodeend;
int wght;
EdgeGraph ()
EdgeGraph (int node_1, int node_2, int weight): nodStart (node_1),
nodeend (node_2), wght (peso)
;
bool compareEdGecost (const EdgeGraph A, const EdgeGraph b)
devolver un.wght < b.wght;

Clase G
privado:
int num_of_nodes;
std :: vector EdgeGraphlist;
std :: vector parentnode;
std :: vector RankNode;
público:
GRAMO()
G (int num_of_nodes)

this-> num_of_nodes = num_of_nodes;
parentnode.cambiar el tamaño (num_of_nodes);
ranknode.cambiar el tamaño (num_of_nodes);

vacío adicional (bordegraph e);
int findparentNode (int nodo);
void kruskalmst_algo (std :: vector&);
void displayEgedgraphs (std :: vector&);
;
void g :: agregadoGraph (EdgeGraph e)
Lista de borde.push_back (e);

int g :: findParentNode (int nodo)
if (nodo != parentNode [nodo])
parentNode [nodo] = findParentNode (parentNode [nodo]);
return ParentNode [nodo];

void g :: displayedgegraphs (std :: vector& mst)
int costo = 0;
std :: cout << "EdgeGraphs of MST : ";
para (auto & e: mst)
std :: cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
Costo += E.wght;

std :: cout << "\n Kruskal MST Cost : " << cost << std :: endl;

// Esta es la función principal de algoritmo de Kruskal que busca
// El árbol de expansión mínimo.
Void G :: Kruskalmst_algo (std :: vector& resultado)
para (int i = 0; iparentNode [i] = i;
RankNode [i] = 0;

ordenar (EdgeGraphlist.begin (), EdgeGraphlist.fin(),
CompareEdGecost);
para (Auto & E: EdgeGraphList)
int root_1 = findParentNode (E.nodStart);
int root_2 = findParentNode (E.nodeend);
if (root_1 != root_2)
resultado.push_back (e);
if (RankNode [root_1] < rankNode[root_2])
parentNode [root_1] = root_2;
RankNode [root_2] ++;
demás
parentNode [root_2] = root_1;
RankNode [root_1] ++;




int main ()
int num_of_nodes = 6; // (0, 1, 2, 3, 4, 5)
EdgeGraph E1 (0, 1, 4);
EdgeGraph E2 (0, 2, 1);
EdgeGraph E3 (0, 3, 5);
EdgeGraph E4 (1, 3, 2);
EdgeGraph E5 (1, 4, 3);
EdgeGraph E6 (1, 5, 3);
EdgeGraph E7 (2, 3, 2);
EdgeGraph E8 (2, 4, 8);
EdgeGraph E9 (3, 4, 1);
EdgeGraph E10 (4, 5, 3);
G G1 (num_of_nodes);
G1.AgregadoGraph (E1);
G1.Se agregógraph (E2);
G1.Se agregógraph (E3);
G1.AgregadoGraph (E4);
G1.Se agregógraph (E5);
G1.Agregadograph (E6);
G1.Agregadograph (E7);
G1.AgregadoGraph (E8);
G1.AgregadoGraph (E9);
G1.AgregadoGraph (E10);
std :: vector MST; // Esto almacenará el árbol de expansión mínimo
G1.Kruskalmst_algo (MST);
G1.DisplayEgedGraphs (MST);
regresar 0;

Producción:

Graphs de MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)
Kruskal MST Costo: 9

Conclusión:

Hemos estudiado el árbol de expansión mínimo de Kruskal, que es la primera preferencia de la mayoría de las personas cuando tienen que encontrar el gráfico MST de un gráfico. El algoritmo de Kruskal es simple de comprender e implementar en una aplicación del mundo real. Al igual que el algoritmo de Prim, el algoritmo de Kruskal también es muy útil en aplicaciones de la vida real. Entonces debemos entender este algoritmo.