Data Structure & Algorithms
Minimum spanning trees con Kruskal y Prim, propiedad de corte y Union-Find con path compression para conectividad y detección de ciclos.
Un minimum spanning tree o MST conecta todos los vértices de un grafo no dirigido y ponderado usando el menor peso total posible, sin formar ciclos.
No busca el camino más corto entre dos puntos. Busca una red completa de conexión con costo total mínimo.
Para un grafo conectado con V vértices, cualquier spanning tree:
V - 1 aristas.Si el grafo no es conectado, no existe un único spanning tree. El resultado equivalente es un minimum spanning forest, uno por componente.
El peso debe representar un costo aditivo coherente. Si importan restricciones como capacidad, dirección o redundancia, un MST puede no modelar el problema real.
Divide los vértices en dos grupos. Entre las aristas que cruzan ese corte, una arista de peso mínimo es segura para algún MST.
Esta propiedad justifica tanto Kruskal como Prim: ambos añaden aristas que pueden incluirse sin perder optimalidad.
Kruskal procesa las aristas de menor a mayor peso y añade una solo si conecta componentes diferentes.
ordenar aristas
→ tomar la más barata
→ comprobar si crea ciclo
→ unir componentes si es seguraPara detectar ciclos de forma eficiente utiliza Union-Find.
type Edge = {
from: number;
to: number;
weight: number;
};
class UnionFind {
private readonly parent: number[];
private readonly rank: number[];
private components: number;
constructor(size: number) {
this.parent = Array.from({ length: size }, (_, index) => index);
this.rank = Array(size).fill(0);
this.components = size;
}
find(value: number): number {
if (this.parent[value] !== value) {
this.parent[value] = this.find(this.parent[value]);
}
return this.parent[value];
}
union(a: number, b: number): boolean {
let rootA = this.find(a);
let rootB = this.find(b);
if (rootA === rootB) return false;
if (this.rank[rootA] < this.rank[rootB]) {
[rootA, rootB] = [rootB, rootA];
}
this.parent[rootB] = rootA;
if (this.rank[rootA] === this.rank[rootB]) {
this.rank[rootA] += 1;
}
this.components -= 1;
return true;
}
connected(a: number, b: number): boolean {
return this.find(a) === this.find(b);
}
countComponents(): number {
return this.components;
}
}
function kruskal(vertexCount: number, edges: Edge[]): Edge[] | null {
const sorted = [...edges].sort((a, b) => a.weight - b.weight);
const unionFind = new UnionFind(vertexCount);
const tree: Edge[] = [];
for (const edge of sorted) {
if (unionFind.union(edge.from, edge.to)) {
tree.push(edge);
if (tree.length === vertexCount - 1) break;
}
}
return tree.length === vertexCount - 1 ? tree : null;
}Después de procesar un prefijo de aristas ordenadas, tree es un bosque sin ciclos que puede extenderse a un MST.
E aristas: O(E log E).O(α(V)) por operación.O(E log E).O(V + E) si se copia y ordena la lista.α es la función inversa de Ackermann y crece tan lentamente que se comporta como una constante para tamaños prácticos, pero no es literalmente O(1) en el análisis formal.
Cada conjunto se representa como un árbol de padres.
0 ← 1 ← 2
find(2) → 0Dos optimizaciones evitan árboles altos:
find conecta los nodos visitados directamente con la raíz.Union-Find responde muy bien:
a y b conectados?;No recupera el camino entre nodos, no calcula distancias y no soporta eliminaciones dinámicas de manera directa.
Prim comienza desde un vértice y hace crecer un árbol. En cada paso toma la arista de menor peso que conecta el árbol actual con un vértice exterior.
Con adjacency list y min-heap:
O(E log V);O(V + E).Prim suele ser cómodo cuando el grafo ya está representado por vecinos. Kruskal suele ser natural cuando tienes una lista de aristas y el grafo es disperso.
Un grafo puede tener varios MST con el mismo costo. Si todos los pesos son distintos, el MST es único. Con empates, el algoritmo puede devolver árboles diferentes según el orden, todos correctos si conservan el costo mínimo.
| Pregunta | MST | Shortest path |
|---|---|---|
| Objetivo | Conectar todos con costo total mínimo | Minimizar el costo de una ruta |
| Resultado | Árbol o bosque | Distancias y predecesores |
| Camino entre dos nodos | No necesariamente el más corto | Sí, según el algoritmo y condiciones |
| Dirección | Normalmente grafo no dirigido | Puede ser dirigido o no dirigido |
find siempre es O(1).V - 1 aristas.¿El camino entre dos vértices dentro de un MST siempre es el camino más corto entre ellos en el grafo original?
No. El MST minimiza la suma de las aristas de toda la red. Puede aceptar un camino más largo entre una pareja si eso reduce el costo global de conectar todos los vértices.