Algoritmo de kruskal: el árbol generador mínimo

El Algoritmo de Kruskal es un concepto que se introduce en la teoría de grafos de las matemáticas discretas. Se utiliza para descubrir el camino más corto entre dos puntos en un grafo conectado y ponderado. Este algoritmo convierte un grafo dado en un bosque, considerando cada nodo como un árbol separado. Estos árboles solo pueden unirse entre sí si la arista que los conecta tiene un valor bajo y no genera un ciclo en la estructura del AGM (Árbol Generador Mínimo). En este tutorial, aprenderás más sobre el Algoritmo de Kruskal en detalle.

¿Qué es el Algoritmo de Kruskal?

El Algoritmo de Kruskal es un algoritmo clásico utilizado en la teoría de grafos para encontrar el Árbol Generador Mínimo (AGM) de un grafo conectado, no dirigido y ponderado. El AGM es un subconjunto de las aristas que conecta todos los vértices sin ningún ciclo y con el peso total mínimo posible de las aristas. El Algoritmo de Kruskal es codicioso, lo que significa que construye el AGM seleccionando siempre la siguiente arista más corta que no forme un ciclo.

Pasos del Algoritmo de Kruskal

1. Ordenar todas las aristas : Comienza ordenando todas las aristas del grafo en orden no decreciente de su peso.
2. Inicializar subconjuntos : Crea un conjunto para cada vértice del grafo. Esto generalmente se hace usando una estructura de datos Disjoint Set Union (DSU) o Union-Find, que ayuda a administrar y fusionar conjuntos de manera eficiente.
3. Iterar sobre las aristas ordenadas : Recorre la lista de aristas ordenadas y, para cada arista, determina si agregarla al árbol generador en crecimiento formaría un ciclo. Esto se hace comprobando si los dos vértices de la arista pertenecen a conjuntos diferentes. Si lo hacen, incluye esta arista en el AGM y une los conjuntos de estos dos vértices. Si pertenecen al mismo conjunto, incluir esta arista formaría un ciclo, por lo que se descarta.
4. Repetir hasta que el AGM esté completo : Continúa el proceso hasta que haya V-1 aristas en el AGM, donde V es el número de vértices en el grafo.

¿Qué es un Árbol Generador?

Un árbol generador es un subconjunto de un grafo que incluye todos los vértices del grafo y algunas de las aristas del grafo original, con la intención de no tener ciclos. Un árbol generador no es necesariamente único; es posible que haya varios árboles generadores para un grafo dado. Sin embargo, un grafo dado siempre tendrá al menos un árbol generador. Las aristas en un árbol generador se llaman "aristas de rama", mientras que las aristas que no están en el árbol generador se llaman "aristas de ciclo". Este tipo de grafo ayuda a encontrar el número mínimo de aristas necesarias para conectar todos los vértices en un grafo. También se utiliza para crear redes mínimamente seguras con rutas redundantes.

¿Qué es un Árbol Generador Mínimo?

Un Árbol Generador Mínimo (AGM) es un subconjunto de las aristas de un grafo conectado, con aristas ponderadas, que conecta todos los vértices juntos sin ningún ciclo y con el peso total mínimo posible de las aristas. Es una forma de encontrar la manera más económica de conectar un conjunto de vértices. Un AGM no es necesariamente único. Todos los pesos de las aristas en el AGM deben ser distintos. Si todos los pesos de las aristas en el grafo son iguales, entonces cualquier árbol generador del grafo es un AGM. Las aristas del AGM se pueden encontrar utilizando el algoritmo codicioso o el algoritmo más sofisticado de Kruskal o Prim.

¿Cuántas aristas tiene un Árbol Generador Mínimo?

Un Árbol Generador Mínimo (AGM) es un subconjunto de las aristas de un grafo conectado, no dirigido, que conecta todos los vértices con el peso total más pequeño posible de las aristas. Un AGM tiene exactamente n-1 aristas, donde n es el número de vértices en el grafo.

Creando un Árbol Generador Mínimo usando el Algoritmo de Kruskal

Primero veremos los pasos involucrados en el Algoritmo de Kruskal para generar un árbol generador mínimo:

1. Paso 1 : Ordena todas las aristas en orden creciente de sus pesos de arista.
2. Paso 2 : Elige la arista más pequeña.
3. Paso 3 : Comprueba si la nueva arista crea un ciclo o un bucle en un árbol generador.
4. Paso 4 : Si no forma el ciclo, incluye esa arista en el AGM. De lo contrario, descártala.
5. Paso 5 : Repite desde el paso 2 hasta que incluya |V| - 1 aristas en el AGM.

Utilizando los pasos mencionados anteriormente, generarás una estructura de árbol generador mínimo. Entonces, ahora echemos un vistazo a un ejemplo para comprender mejor este proceso. El grafo G(V, E) dado a continuación contiene 6 vértices y 12 aristas. Y crearás un árbol generador mínimo T(V', E') para G(V, E) de modo que el número de vértices en T sea 6 y las aristas sean 5 (6-1).

Ejemplo

Si observas este grafo, encontrarás dos aristas de bucle que conectan el mismo nodo consigo mismo nuevamente. Y sabes que la estructura del árbol nunca puede incluir un bucle o una arista paralela. Por lo tanto, primero debes eliminar estas aristas de la estructura del grafo. El siguiente paso que realizarás es organizar todas las aristas en una lista ordenada por sus pesos de arista.

Después de este paso, incluirás aristas en el AGM de modo que la arista incluida no genere un ciclo en la estructura de tu árbol. La primera arista que elegirás es la arista EF, ya que tiene un peso de arista mínimo que es Agrega la arista FD al árbol generador. Agrega la arista BC y la arista CF al árbol generador ya que no genera ningún bucle. La siguiente es la arista CD. Esta arista genera el bucle en la estructura de tu árbol. Por lo tanto, descartarás esta arista. Después de la arista CD, tienes la arista BF. Esta arista también crea el bucle; por lo tanto, la descartarás. La siguiente es la arista BD. Esta arista también formula un bucle, por lo que también la descartarás. La siguiente en tu lista ordenada es la arista AB. Esta arista no genera ningún ciclo, por lo que no necesitas incluirla en la estructura del AGM. Al incluir este nodo, incluirá 5 aristas en el AGM, por lo que no tienes que recorrer más en la lista ordenada. La estructura final de tu AGM se representa en la imagen a continuación:

La suma de todos los pesos de las aristas en el AGM T(V', E') es igual a 17, que es el peso de arista menor posible para cualquier posible estructura de árbol generador para este grafo en particular.

¿Qué es el Algoritmo Union-Find?

Union-Find es un algoritmo que lleva un registro de los elementos que se dividen en uno o más conjuntos disjuntos. Tiene dos operaciones principales: Find y Union. La operación Find devuelve el conjunto de elementos al que pertenece el elemento dado (argumento), mientras que la operación Union fusiona dos conjuntos disjuntos. Debes dividir el grafo G(V, E) dado en tres conjuntos separados mientras construyes el Árbol Generador Mínimo usando el enfoque de Kruskal. El primero contiene valores de peso de arista, el segundo tiene una jerarquía de árbol para nodos distintos y el tercero incluye el rango de todos los nodos. Mediante el uso de las operaciones Union y Find, une los nodos distintos, que se tratan como árboles diferentes, para formular un árbol generador mínimo.

Implementación del Algoritmo de Kruskal en C

Cualquier algoritmo de AGM gira en torno a determinar si agregar una arista resultaría en un bucle o no. Union-Find es el algoritmo más popular para determinar esto. El algoritmo Union-Find separa los vértices en clústeres, lo que te permite determinar si dos vértices pertenecen al mismo clúster y, por lo tanto, si agregar una arista producirá un ciclo. La estrategia para implementar el algoritmo de Kruskal usando Union-Find se da a continuación:

1. Construye una estructura para llevar un registro de los nodos de origen y destino, así como su peso.
2. Ordena todas las aristas de un grafo según sus valores de peso de arista.
3. Crea tres conjuntos distintos para mantener los nodos de un grafo, su jerarquía en un árbol y los rangos correspondientes para cada nodo.
4. Principalmente, inicializa todos los valores de rango a 0 y los valores padre a -1 (representando cada nodo como su propio árbol).
5. Para cada inserción de una arista en el AGM, actualizarás el rango y el padre de cada nodo.
6. No insertes la arista que conecta dos nodos si tienen el mismo nodo padre, ya que esto causará un ciclo en la estructura del árbol.

Ahora, comprenderás esta estrategia de implementación con la ayuda de un ejemplo. El grafo para el que desarrollarás un árbol generador mínimo usando el enfoque de Kruskal se da a continuación:

Inicialmente, debes crear dos conjuntos para mantener el valor padre y el valor de rango para cada nodo. Junto con eso, crearás una estructura para mantener las aristas del grafo. Para todos los nodos del grafo, inicializarás los valores padre a -1 y los valores de rango a 0. La razón de esto es que necesitas tratar todos los nodos de un grafo como árboles en sí mismos. Además, recuerda que siempre que unas dos estructuras de árbol disjuntas, el rango del que se apunta aumentará en uno. Entonces, una vez que agregues aristas al AGM, el rango y los valores padre de los nodos incluidos cambiarán. Este grafo en particular mostrará el estado de los conjuntos, como la figura a continuación.

El programa C para implementar el algoritmo de Kruskal usando la estrategia mencionada anteriormente es el siguiente:

#include #include #include // Estructura que denota una arista ponderadastruct Edge { int source, destination, weight;};// Estructura que denota un grafo ponderado, no dirigido y conectadostruct Graph { int Node, E; struct Edge edge;};// Asigna memoria para almacenar el grafo con V vértices y E aristasstruct Graph GenerateGraph(int Node, int E) { struct Graph graph = (struct Graph)(malloc(sizeof(struct Graph))); graph->Node = Node; graph->E = E; graph->edge = (struct Edge)malloc(sizeof(struct Edge)); return graph;}// Subconjunto para Union-Findstruct tree_maintainance_set { int parent; int rank;};// Encuentra el conjunto del elemento elegido i utilizando la compresión de rutaint find_DisjointSet(struct tree_maintainance_set subsets[], int I) { // Encuentra la raíz y haz que la raíz sea el padre de i if (subsets[i].parent != i) subsets[i].parent = find_DisjointSet(subsets, subsets[i].parent); return subsets[i].parent;}// Crea la unión de dos conjuntosvoid Union_DisjointSet(struct tree_maintainance_set subsets[], int x, int y) { int xroot = find_DisjointSet(subsets, x); int yroot = find_DisjointSet(subsets, y); // Conectando el árbol con el rango más bajo al árbol con el rango más alto if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; // Si los rangos son iguales, aumenta arbitrariamente el rango de un nodo else { subsets[yroot].parent = xroot; subsets[xroot].rank++; }}// Función para comparar aristas usando qsort() en programación Cint myComp(const void a, const void b) { struct Edge a1 = (struct Edge)a; struct Edge b1 = (struct Edge)b; return a1->weight > b1->weight;}// Función para construir el AGM utilizando el enfoque de Kruskalvoid KruskalMST(struct Graph graph) { int Node = graph->Node; struct Edge result[Node]; int e = 0; int i = 0; // Ordenando todas las aristas qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp); // Asignación de memoria para V subconjuntos struct tree_maintainance_set subsets = (struct tree_maintainance_set)malloc(Node sizeof(struct tree_maintainance_set)); // V subconjuntos que contienen solo un elemento for (int v = 0; v < Node; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } // Límite de recorrido de aristas: V-1 while (e < Node - 1 && i < graph->E) { struct Edge next_edge = graph->edge[i++]; int x = find_DisjointSet(subsets, next_edge.source); int y = find_DisjointSet(subsets, next_edge.destination); if (x != y) { result[e++] = next_edge; Union_DisjointSet(subsets, x, y); } } // Imprimiendo AGM printf("Las aristas creadas en el AGM son las siguientes:"); int minimumCost = 0; for (i = 0; i < e; ++i) { printf("%d -- %d == %d", result[i].source, result[i].destination, result[i].weight); minimumCost += result[i].weight; } printf("El costo del AGM creado es: %d", minimumCost); return;}int main() { int Node = 4; int E = 6; struct Graph graph = GenerateGraph(Node, E); // Creando el grafo con inserción manual de valores // Agrega la arista 0-1 graph->edge[0].source = 0; graph->edge[0].destination = 1; graph->edge[0].weight = 2; // Agrega la arista 0-2 graph->edge[1].source = 0; graph->edge[1].destination = 2; graph->edge[1].weight = 4; // Agrega la arista 0-3 graph->edge[2].source = 0; graph->edge[2].destination = 3; graph->edge[2].weight = 4; // Agrega la arista 1-3 graph->edge[3].source = 1; graph->edge[3].destination = 3; graph->edge[3].weight = 3; // Agrega la arista 2-3 graph->edge[4].source = 2; graph->edge[4].destination = 3; graph->edge[4].weight = 1; // Agrega la arista 1-2 graph->edge[5].source = 1; graph->edge[5].destination = 2; graph->edge[5].weight = 2; KruskalMST(graph); return 0;}// Salida:// Puedes verificar la precisión de esta salida comparándola con la estructura del AGM que se muestra arriba.// El costo total de este AGM es

Implementación del Algoritmo de Kruskal en C++

#include #include #include using namespace std;// Define una estructura de aristastruct Edge { int src, dest, weight;};// Una clase para representar un grafoclass Graph { public: int V, E; // V -> número de vértices, E -> número de aristas vector edges; // colección de todas las aristas Graph(int V, int E); void addEdge(int u, int v, int w); int find(vector & parent, int i); void Union(vector & parent, vector & rank, int x, int y); void kruskalMST();};// ConstructorGraph::Graph(int V, int E) { this->V = V; this->E = E; edges.resize(E);}// Función para agregar una arista al grafovoid Graph::addEdge(int u, int v, int w) { Edge edge = {u, v, w}; edges.push_back(edge);}// Una función de utilidad para encontrar el conjunto de un elemento i (utiliza la técnica de compresión de ruta)int Graph::find(vector & parent, int i) { if (parent[i] != i) { parent[i] = find(parent, parent[i]); } return parent[i];}// Una función que realiza la unión de dos conjuntos de x e y (utiliza la unión por rango)void Graph::Union(vector & parent, vector & rank, int x, int y) { int xroot = find(parent, x); int yroot = find(parent, y); if (rank[xroot] < rank[yroot]) { parent[xroot] = yroot; } else if (rank[xroot] > rank[yroot]) { parent[yroot] = xroot; } else { parent[yroot] = xroot; rank[xroot]++; }}// La función principal para construir el AGM utilizando el algoritmo de Kruskalvoid Graph::kruskalMST() { vector result; // Almacena el AGM resultante int e = 0; // Una variable de índice, utilizada para result[] int i = 0; // Una variable de índice, utilizada para aristas ordenadas // Paso 1: Ordena todas las aristas en orden no decreciente de su peso. sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.weight < b.weight; }); // Asigna memoria para crear V subconjuntos vector parent(V); vector rank(V, 0); // Crea V subconjuntos con elementos únicos for (int v = 0; v < V; ++v) { parent[v] = v; } // El número de aristas que se tomarán es igual a V-1 while (e < V - 1 && i < edges.size()) { // Paso 2: Elige la arista más pequeña. Y aumenta el índice para la siguiente iteración Edge next_edge = edges[i++]; int x = find(parent, next_edge.src); int y = find(parent, next_edge.dest); // Si incluir esta arista no causa un ciclo, inclúyela en result // y aumenta el índice de result para la siguiente arista if (x != y) { result.push_back(next_edge); Union(parent, rank, x, y); e++; } // De lo contrario, descarta la siguiente arista } // Imprime el AGM resultante cout << "Las siguientes son las aristas en el AGM construido"; for (const auto& edge : result) { cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl; }}int main() { int V = 4; // Número de vértices en el grafo int E = 5; // Número de aristas en el grafo Graph graph(V, E); // Agrega aristas graph.addEdge(0, 1, 10); graph.addEdge(0, 2, 6); graph.addEdge(0, 3, 5); graph.addEdge(1, 3, 15); graph.addEdge(2, 3, 4); // Llamada a la función graph.kruskalMST(); return 0;}// Explicación// Estructura de arista: Define una arista con origen (src), destino (dest) y peso (weight).// Clase Graph: Contiene vértices (V), aristas (E) y una colección de aristas (edges).// Funciones para agregar aristas, encontrar el conjunto de un elemento, unión de dos conjuntos y la función principal para calcular el AGM (kruskalMST).// addEdge: Agrega una arista al grafo.// find: Encuentra el representante (raíz) del conjunto del que forma parte el elemento i, con compresión de ruta para acelerar las consultas futuras.// Union: Une dos conjuntos (x e y), utilizando la unión por rango para mantener el árbol plano.// kruskalMST: Ordena las aristas por peso; Utiliza una estructura union-find para administrar conjuntos disjuntos; Itera a través de las aristas, agregándolas al AGM si no forman un ciclo, hasta que el AGM contiene V-1 aristas.// Función principal: Crea un grafo, agrega aristas y llama a kruskalMST para encontrar e imprimir el AGM.

Implementación del Algoritmo de Kruskal en Python

# Paso 1: Define la estructura de datos Union-Find (Disjoint Set)class DisjointSet: def __init__(self, vertices): self.parent = {v: v for v in vertices} self.rank = {v: 0 for v in vertices} def find(self, item): if self.parent[item] == item: return item else: self.parent[item] = self.find(self.parent[item]) return self.parent[item] def union(self, set1, set2): root1 = self.find(set1) root2 = self.find(set2) if root1 != root2: if self.rank[root1] > self.rank[root2]: self.parent[root2] = root1 elif self.rank[root1] < self.rank[root2]: self.parent[root1] = root2 else: self.parent[root2] = root1 self.rank[root1] += 1# Paso 2: Define el Algoritmo de Kruskaldef kruskal(vertices, edges): # Ordena las aristas por peso edges = sorted(edges, key=lambda edge: edge[2]) # Inicializa Disjoint Set disjoint_set = DisjointSet(vertices) mst = [] for edge in edges: u, v, weight = edge # Comprueba si incluir esta arista formaría un ciclo if disjoint_set.find(u) != disjoint_set.find(v): disjoint_set.union(u, v) mst.append(edge) return mst# Paso 3: Ejemplo de uso# Lista de vértices en el grafovertices = ['A', 'B', 'C', 'D', 'E']# Lista de aristas en el grafo (u, v, peso)edges = [ ('A', 'B', 1), ('A', 'C', 3), ('B', 'C', 3), ('B', 'D', 6), ('C', 'D', 4), ('C', 'E', 2), ('D', 'E', 5),]# Calcula el Árbol Generador Mínimo utilizando el Algoritmo de Kruskalmst = kruskal(vertices, edges)# Imprime el resultadoprint("Aristas en el Árbol Generador Mínimo:")for edge in mst: print(edge)# Explicación# Clase Disjoint Set:# Inicialización: Crea un puntero padre y un rango para cada vértice;# Operación Find: Implementa la compresión de ruta para encontrar la raíz de un conjunto;# Operación Union: Utiliza la unión por rango para adjuntar árboles de menor profundidad bajo la raíz de árboles más profundos.# Algoritmo de Kruskal:# Ordenar aristas: Ordena las aristas en función de sus pesos en orden ascendente;# Inicialización de Disjoint Set: Crea conjuntos disjuntos para cada vértice;# Selección de aristas: Itera a través de las aristas ordenadas e incluye una arista en el AGM si no forma un ciclo;# Devolver AGM: El AGM se devuelve como una lista de aristas.# Ejemplo de uso: Define vértices y aristas; Llama a la función Kruskal e imprime las aristas del AGM.

Implementación del Algoritmo de Kruskal en Java

import java.util.;class Edge implements Comparable { int src, dest, weight; // Función comparadora utilizada para ordenar aristas en función de su peso public int compareTo(Edge compareEdge) { return this.weight - compareEdge.weight; }};class Subset { int parent, rank;};class Graph { int V, E; // Número de vértices y aristas Edge[] edges; // Colección de todas las aristas Graph(int v, int e) { V = v; E = e; edges = new Edge[E]; for (int i = 0; i < e; ++i) { edges[i] = new Edge(); } } // Una función de utilidad para encontrar el conjunto de un elemento i (utiliza la compresión de ruta) int find(Subset[] subsets, int i) { if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } // Una función que realiza la unión de dos conjuntos de x e y (utiliza la unión por rango) void union(Subset[] subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); // Adjunta el árbol de rango más pequeño bajo la raíz del árbol de rango más alto if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } // La función principal para construir el AGM utilizando el algoritmo de Kruskal void kruskalMST() { Edge[] result = new Edge[V]; // Esto almacenará el AGM resultante int e = 0; // Una variable de índice, utilizada para result[] int i = 0; // Una variable de índice, utilizada para aristas ordenadas for (i = 0; i < V; ++i) result[i] = new Edge(); // Paso 1: Ordena todas las aristas en orden no decreciente de su peso. Arrays.sort(edges); // Asigna memoria para crear V subconjuntos Subset[] subsets = new Subset[V]; for (i = 0; i < V; ++i) subsets[i] = new Subset(); // Crea V subconjuntos con elementos únicos for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // Índice utilizado para elegir la arista más pequeña // El número de aristas que se tomarán es igual a V-1 while (e < V - 1) { // Paso 2: Elige la arista más pequeña. Y aumenta el índice para la siguiente iteración Edge nextEdge = edges[i++]; int x = find(subsets, nextEdge.src); int y = find(subsets, nextEdge.dest); // Si incluir esta arista no causa un ciclo, inclúyela en result // y aumenta el índice de result para la siguiente arista if (x != y) { result[e++] = nextEdge; union(subsets, x, y); } // De lo contrario, descarta la siguiente arista } // Imprime el contenido de result[] para mostrar el AGM construido System.out.println("Las siguientes son las aristas en el AGM construido:"); for (i = 0; i < e; ++i) System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight); }}public class Kruskal { public static void main(String[] args) { int V = 4; // Número de vértices en el grafo int E = 5; // Número de aristas en el grafo Graph graph = new Graph(V, E); // Agrega la arista 0-1 graph.edges[0].src = 0; graph.edges[0].dest = 1; graph.edges[0].weight = 10; // Agrega la arista 0-2 graph.edges[1].src = 0; graph.edges[1].dest = 2; graph.edges[1].weight = 6; // Agrega la arista 0-3 graph.edges[2].src = 0; graph.edges[2].dest = 3; graph.edges[2].weight = 5; // Agrega la arista 1-3 graph.edges[3].src = 1; graph.edges[3].dest = 3; graph.edges[3].weight = 15; // Agrega la arista 2-3 graph.edges[4].src = 2; graph.edges[4].dest = 3; graph.edges[4].weight = 4; graph.kruskalMST(); }}// Explicación// Clase Edge: Esta clase representa una arista con origen, destino y peso. Es comparable para ordenar aristas por peso.// Clase Subset: Representa un subconjunto para union-find.// Clase Graph: Contiene métodos para encontrar el AGM utilizando el algoritmo de Kruskal.// find(): Utiliza la compresión de ruta.// union(): Utiliza la unión por rango.// kruskalMST(): Método principal para realizar el algoritmo de Kruskal.// Método principal: Inicializa el grafo, agrega aristas y llama a kruskalMST().

Algoritmo de Kruskal vs Algoritmo de Prim

Algoritmo de Kruskal

El algoritmo codicioso de Kruskal encuentra un árbol generador mínimo para un grafo ponderado, no dirigido. El algoritmo comienza con un bosque que consiste en los nodos individuales del grafo y luego encuentra la arista más barata de cada nodo y la agrega al bosque. Este proceso se repite hasta que solo queda un árbol en el bosque, el árbol generador mínimo. El algoritmo de Kruskal es un algoritmo de árbol generador mínimo que toma un grafo como entrada y encuentra el subconjunto de las aristas de ese grafo. Esta entrada forma un árbol que incluye cada vértice, donde el peso total de todas las aristas del árbol se minimiza. El algoritmo funciona ordenando las aristas del grafo por peso, luego tomando la arista con el peso más bajo del grafo y agregándola al árbol. Este proceso se repite hasta que todos los vértices se incluyen en el árbol.

Algoritmo de Prim

El algoritmo de Prim también es codicioso y encuentra un árbol generador mínimo para un grafo ponderado, no dirigido. Sin embargo, el algoritmo comienza con un solo nodo y luego agrega la arista más barata desde ese nodo al árbol. Pero el algoritmo de Prim funciona de manera diferente al algoritmo de Kruskal. Y este proceso se repite hasta que hay n-1 aristas en el árbol, donde n es el número de nodos en el grafo.

Complejidad del Algoritmo de Kruskal

El algoritmo de Kruskal es un algoritmo bien conocido para encontrar el árbol generador mínimo de un grafo. Es un algoritmo codicioso que utiliza el hecho de que las aristas de un árbol generador mínimo deben formar un subconjunto de las aristas de cualquier otro árbol generador. La complejidad temporal del Algoritmo de Kruskal es O(ElogE), donde E es el número de aristas en el grafo. Esta complejidad se debe a que el algoritmo utiliza una cola de prioridad con una complejidad temporal de O(logE). Sin embargo, la complejidad espacial del algoritmo es O(E), que es relativamente alta.

Aplicaciones del Algoritmo de Kruskal

El algoritmo de

Si quieres conocer otros artículos parecidos a Algoritmo de kruskal: el árbol generador mínimo puedes visitar la categoría Arboles y plantas.