Árbol de Expansión Mínima (MST)

¿Qué es un MST?

Analogía: Necesitas conectar varias ciudades con carreteras gastando lo menos posible. No necesitas todas las carreteras posibles — solo las suficientes para que todas las ciudades estén conectadas. El Árbol de Expansión Mínima (Minimum Spanning Tree) es exactamente eso: un subconjunto de aristas que conecta todos los nodos con el menor peso total.

Propiedades:

• Tiene exactamente $n - 1$ aristas (es un árbol).
• Conecta todos los $n$ nodos.
• El peso total es el mínimo posible.

Kruskal: ordenar y unir

1. Ordena todas las aristas por peso (de menor a mayor).
2. Para cada arista, si conecta dos componentes diferentes, agrégala.
3. Usa Union-Find para verificar componentes.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Arista {
    int u, v, w;
    bool operator<(const Arista &o) const { return w < o.w; }
};

int padre[100005], rk[100005];

int encontrar(int x) {
    if (padre[x] != x) padre[x] = encontrar(padre[x]);
    return padre[x];
}

bool unir(int a, int b) {
    a = encontrar(a); b = encontrar(b);
    if (a == b) return false;
    if (rk[a] < rk[b]) swap(a, b);
    padre[b] = a;
    if (rk[a] == rk[b]) rk[a]++;
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<Arista> aristas(m);
    for (auto &[u, v, w] : aristas) cin >> u >> v >> w;

    sort(aristas.begin(), aristas.end());

    for (int i = 1; i <= n; i++) { padre[i] = i; rk[i] = 0; }

    long long costoTotal = 0;
    int aristasUsadas = 0;

    for (auto &[u, v, w] : aristas) {
        if (unir(u, v)) {
            costoTotal += w;
            aristasUsadas++;
            if (aristasUsadas == n - 1) break;
        }
    }

    if (aristasUsadas == n - 1) {
        cout << "Costo MST: " << costoTotal << endl;
    } else {
        cout << "No es posible conectar todos los nodos" << endl;
    }

    return 0;
}

Complejidad: $O(E \log E)$ por el ordenamiento.

Prim: expandir desde un nodo

Similar a Dijkstra: empieza desde un nodo y siempre agrega la arista más barata que conecte un nodo nuevo.

#include <queue>

typedef pair<int,int> pii;
vector<pii> adj[100005];
bool enMST[100005];

long long prim(int n) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 1});
    long long costo = 0;
    int nodos = 0;

    while (!pq.empty() && nodos < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (enMST[u]) continue;

        enMST[u] = true;
        costo += w;
        nodos++;

        for (auto [v, peso] : adj[u]) {
            if (!enMST[v]) {
                pq.push({peso, v});
            }
        }
    }

    return (nodos == n) ? costo : -1;
}

Complejidad: $O((V + E) \log V)$

¿Kruskal o Prim?

Ejercicio de práctica

Conecta N ciudades con carreteras de costo mínimo. Imprime el costo total.

Ver solución

Usa Kruskal (el código completo está arriba). Lee las aristas, ordena, y aplica Union-Find.