Materia: #técnicas_y_diseños_de_algoritmos

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

Algoritmo de Prim

Una de las implementaciones mas conocidas para encontrar un árbol generador mínimo es el algoritmo de Prim, que podria escribirse en pseudocodigo de la siguiente manera:

Prim(G, I):
	Vt = {u}; // siendo u cualquier nodo de G
	Xt = {};
	i = 1;
	while () do:
		elegir e = (u,v) en X tal que l(e) sea mínima entre las aristas que tienen un extremo u en Vt y el otro v en V sin Vt
		Xt = Xt + {e};
		Vt = Vt + {v};
		i = i + 1;
	end while;
	return T = (Vt, Xt);

Donde $G=(V,X)$ es un grafo conexo, e $I$ es una función $X\to \mathbb{R}$.

Explicado en criollo, este algoritmo basicamente lo que hace es pararse en algun nodo, y elegir el camino con el menor peso. Luego, compara todas las aristas del primer nodo, y del vecino del primero que eligio antes, volviendo a elegir al mínimo. Esto lo hace iteradas veces, hasta contener todos los nodos del grafo $G$.

Este algoritmo tiene una complejidad de $O(n^2)$ si se implementa de manera directa y con listas. Si lo implementamos con heaps binarios, podemos reducir la complejidad a $O((m+n)\log n)$, esto conviene cuando el grafo $G$ no es demasiado denso. Por ultimo, tambien existe una implementación mas, utlizando un heap fibonacci, que tiene complejidad amortizada de $O(m+n\log n)$.