Алгоритми Прим
Графи вазндори ғайрисамтдор бо қулла ва канор дода шудааст. Лозим аст дарахти остовии ин графро ёфт, ки ҳамаи қуллаҳоро пайваст мекунад ва вазни умумии ҳадди ақал дорад (яъне суммаи вазнҳои канорҳо минималӣ аст).
Қуллаи ихтиёрии -ро интихоб мекунем. Маҷмӯае месозем, ки аз як қуллаи иборат аст, яъне . Баъдан итератсия иҷро мекунем:
Дар ниҳоят канорҳои интихобшуда дарахтро ташкил медиҳанд — ин ҳамон дарахти остовии минималии ҷустуҷӯшаванда хоҳад буд.
Агар граф аз аввал пайваст набошад, пас дарахти остовие, ки ҳамаи қуллаҳоро дар бар гирад, вуҷуд надорад, бинобар ин шумораи канорҳои интихобшуда аз камтар хоҳад буд.
struct Edge {
int to;
long long weight;
};
int n; // шумораи қуллаҳо
vector<Edge> v[N]; // рӯйхати ҳамсоягӣ
long long prim() {
const long long INF = 1e1e8;
vector<long long> dist(n + 1, INF); // вазни минималии канор то қулла
vector<bool> used(n + 1, false); // оё қулла ба MST дохил мешавад
// (вазн, қулла)
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;
}