Алгоритм Прима
Дан взвешенный неориентированный граф с вершинами и рёбрами. Требуется найти остовное дерево этого графа, которое соединяет все вершины и имеет наименьший суммарный вес (то есть сумма весов рёбер минимальна).
Выбираем произвольную вершину . Создаём множество, состоящее из одной вершины , то есть . Далее выполняем итераций:
В конечном итоге выбранные рёбра образуют дерево — это и будет искомое минимальное остовное дерево.
Если граф изначально не был связным, то остовного дерева, содержащего все вершины, не существует, поэтому количество выбранных рёбер будет меньше, чем .
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;
}