Algoritmo de Kruskal: Una
Exploración Detallada
En esta presentación, exploraremos el algoritmo de Kruskal, un algoritmo
fundamental en la teoría de grafos, que se utiliza para encontrar el árbol de
expansión mínimo de un grafo.
Definición y Características
Definición Características
El algoritmo de Kruskal es un algoritmo voraz que encuentra el El algoritmo de Kruskal se basa en el principio de agregar la
árbol de expansión mínimo (MST) de un grafo conexo, es arista con menor costo al MST en cada paso, siempre y
decir, un árbol que conecta todos los vértices del grafo con el cuando no forme un ciclo.
menor costo total posible.
Pasos del Algoritmo
1 Paso 1 2 Paso 2
Ordena todas las aristas del Inicializa el MST vacío.
grafo en orden ascendente
de costo.
3 Paso 3 4 Paso 4
Selecciona la arista de menor Repite el paso 3 hasta que
costo que no forme un ciclo se hayan agregado n-1
con las aristas ya agregadas aristas al MST, donde n es el
al MST. número de vértices en el
grafo.
Ejemplos de Aplicación
Redes
1 Encontrar rutas de comunicación óptimas en redes.
Infraestructura
2
Diseño de redes de carreteras o líneas eléctricas.
Informática
3
Optimización de algoritmos de enrutamiento de datos.
Ventajas y Desventajas
Ventajas Desventajas
Es relativamente fácil de implementar, funciona bien para Puede ser lento para grafos densos, requiere un proceso de
grafos con un gran número de aristas, produce soluciones clasificación inicial, no es eficiente para grafos no conexos.
óptimas.
Complejidad Computacional
O(E log E) O(V)
Tiempo Espacio
La complejidad temporal del La complejidad espacial del
algoritmo de Kruskal es O(E log E), algoritmo de Kruskal es O(V), donde
donde E es el número de aristas en V es el número de vértices en el
el grafo. grafo.
Implementación en Python
import heapq
def kruskal(graph):
mst = []
edges = sorted(graph.edges, key=lambda edge: edge[2])
parent = {node: node for node in graph.nodes}
rank = {node: 0 for node in graph.nodes}
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(node1, node2):
root1 = find(node1)
root2 = find(node2)
if rank[root1] < rank[root2]:
parent[root1] = root2
elif rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
rank[root2] += 1
for edge in edges:
node1, node2, cost = edge
if find(node1) != find(node2):
mst.append(edge)
union(node1, node2)
return mst
VENTAJAS:
Fácil de implementar, especialmente en grafos dispersos.
Independiente del nodo inicial.
Eficiente con estructuras como Union-Find (O(ElogE)O(E \log E)O(ElogE)).
Funciona en grafos conexos y no conexos.
DESVENTAJAS:
Requiere ordenar las aristas (costoso en grafos densos).
Menos eficiente en grafos con muchas aristas.
Depende de estructuras auxiliares como Union-Find.
No se adapta bien a grafos dinámicos.
Conclusiones y Consideraciones
Finales
Teoría de Grafos
El algoritmo de Kruskal es una herramienta esencial para resolver problemas de optimización en la
teoría de grafos.
Eficiencia
Su eficiencia depende de la densidad del grafo y la selección de la estructura de datos adecuada.
Implementación
La implementación en Python es relativamente sencilla, pero requiere un entendimiento del
algoritmo.
