Prim's Algorithm
A weighted undirected graph with vertices and edges is given. It is required to find a spanning tree of this graph that connects all vertices and has the smallest total weight (that is, the sum of the edge weights is minimal).
Choose an arbitrary vertex . Create a set consisting of a single vertex , that is . Next, perform iterations:
In the end, the selected edges form a tree — this will be the desired minimum spanning tree.
If the graph was not connected initially, then a spanning tree containing all vertices does not exist, so the number of selected edges will be less than .
struct Edge {
int to;
long long weight;
};
int n; // number of vertices
vector<Edge> v[N]; // adjacency list
long long prim() {
const long long INF = 1e1e8;
vector<long long> dist(n + 1, INF); // minimum edge weight to the vertex
vector<bool> used(n + 1, false); // whether the vertex is in the MST
// (weight, vertex)
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;
}