Materia: #técnicas_y_diseños_de_algoritmos

Tags: Algoritmo, Árbol generador mínimo, Grafos, Arboles

Algoritmo de Kruskal

Otra implementación de algoritmos de busqueda de arboles generadores minimos consiste en el algoritmo de Kruskal. El pseudocodigo podria escribirse como:

Kruskal(G, I):
	Xt = {};
	i = 1;
	
	while (i <= n - 1) do:
		elegir e en X tal que l(e) sea mínima entre las aristas que no forman circuito con las aristas que ya están en Xt;
		Xt = Xt + {e};
		i = i + 1;
	end while;
	
	return T = (Vt, Xt)

De algún modo, es una optimización del algoritmo de Prim, tanto en tiempo como en uso de memoria, ya que utiliza menos variables y recorre de manera mas eficiente.

Este algoritmo tiene, de manera trivial, una complejidad de $O(m\ast n)$, pero puede mejorar. Si utilizamos el enfoque union and find, puede reducirse a $O(m\log n)$.