En el problema de árbol generador mínimo (AGM) de $G = (V, E)$ buscamos un subconjunto de aristas $T \subseteq E$ que conecte todos los nodos y cuyo peso total

$$ w(T) = \sum_{(u,v)\in T} w(u,v) $$

sea minimal.

Como $T$ debe ser acíclico para tener peso mínimo y conecta todos los vértices forma un árbol.

Método genérico para desarrollar AGMs

Sea $G = (V, E)$ un grafo conexo y no dirigido con una función de peso $w: E \to \R$.

Ambos algoritmos para encontrar un AGM de $G$ utilizan una estrategia greedy, pero varían en su manera de aplicarla. Esta estrategia consiste en construíir el AGM de a una arista por vez y se ve reflejada en el procedimiento GENERIC-MST(G, w) que mostraremos a continuación.

Pseudocódigo

GENERIC-MST(G, w)
1	  A = emptySet
2	  while A no forma un árbol generador:
3		  busca una arista (u,v) segura para A
4		  A = A ++ {(u, v})}
5	  return A

Invariante

Antes de cada iteración $A$ es un subconjunto de algún AGM de $G$.

Además:

• En cada paso determinamos una arista que podamos agregar a $A$ sin romper el invariante del ciclo. A esta arista la denominamos una arista segura para $A$.
• En cada iteración sabemos que existe una arista segura ya que $A$ es un subconjunto propio de $T$ por la guarda del while.