Prim algoritmi
ta cho‘qqi va ta qirraga ega bo‘lgan og‘irlikli yo‘naltirilmagan graf berilgan. Talab qilinadi: ushbu grafning barcha cho‘qqilarini bog‘laydigan va umumiy og‘irligi eng kichik bo‘lgan (ya’ni qirralar og‘irliklari yig‘indisi minimal) qamrovchi daraxtini topish.
Ixtiyoriy cho‘qqini tanlaymiz. Faqat bitta cho‘qqidan iborat to‘plam yaratamiz, ya’ni . So‘ng ta iteratsiya bajariladi:
Oxir-oqibat tanlangan qirralar daraxt hosil qiladi — bu izlanayotgan minimal qamrovchi daraxt bo‘ladi.
Agar graf dastlab bog‘langan bo‘lmagan bo‘lsa, barcha cho‘qqilarni o‘z ichiga olgan qamrovchi daraxt mavjud emas, shuning uchun tanlangan qirralar soni dan kichik bo‘ladi.
struct Edge {
int to;
long long weight;
};
int n; // cho‘qqilar soni
vector<Edge> v[N]; // qo‘shnichilik ro‘yxati
long long prim() {
const long long INF = 1e1e8;
vector<long long> dist(n + 1, INF); // cho‘qqigacha bo‘lgan qirraning minimal og‘irligi
vector<bool> used(n + 1, false); // cho‘qqi MST ga kiradimi
// (og‘irlik, cho‘qqi)
priority_queue<
pair<long long, int>,
vector<pair<long long, int>>,
greater<pair<long long, int>>
> q;
dist[1] = 0;
q.push({0, 1});
long long mst_weight = 0;
while (!q.empty()) {
int x = q.top().second;
int w = q.top().first;
q.pop();
if (used[x]) {
continue;
}
used[x] = true;
mst_weight += w;
for (Edge e : v[x]) {
if (!used[e.to] && e.weight < dist[e.to]) {
dist[e.to] = e.weight;
q.push({e.weight, e.to});
}
}
}
return mst_weight;
}