Prim (MST)

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Árbol de expansión mínima creciendo desde un vértice y agregando siempre la arista más barata hacia un vértice nuevo.

Complejidad: O(E log V) con priority_queue.

Cuándo usarlo

MST, igual que Kruskal. Prim conviene en grafos densos o dados por lista de adyacencia; Kruskal si tienes la lista de aristas.

Implementación recomendada (C++)

long long prim(int n, const vector<vector<pair<int,int>>>& g) {  // g[u] = {vecino, peso}
    vector<char> in(n, 0);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 0});
    long long cost = 0; int cnt = 0;
    while (!pq.empty() && cnt < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (in[u]) continue;
        in[u] = 1; cost += w; cnt++;
        for (auto [v, ww] : g[u]) if (!in[v]) pq.push({ww, v});
    }
    return cnt == n ? cost : -1;            // -1 si el grafo no es conexo
}

🔗 Relacionados