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
}