Prim's Algorithm

Prim’s Algorithm is an algorithm that computes the weight of the minimum spanning tree of a connected undirected graph $G=(V,E)$ with edge weights in

• $\mathcal{O}(|V{|}^2+|E|)$ time and $\mathcal{O}(|E|)$ space, or
• $\mathcal{O}(|E|\log |E|)$ time and $\mathcal{O}(|E|)$ space.

Tip

This problem can also be solved by Kruskal’s Algorithm in $\mathcal{O}(|E|\log |E|)$ time and $\mathcal{O}(|E|)$ space.

Tip

This problem can also be solved by Boruvka’s Algorithm in $\mathcal{O}(|E|\log |V|)$ time and $\mathcal{O}(|E|)$ space.

Algorithm 0

Lemma

Let $\mathcal{T}$ denote the set of minimum spanning trees of $G$, $\delta (v)$ denote the set of edges incident with $v$. Then

$$\forall v\in V,\forall e\in \arg \underset{e\in \delta (v)}{\min }w(e),\exists T\in \mathcal{T},e\in E(T)$$

Proof

Let $T$ be an arbitrary minimum spanning tree of $G$.

If $e\notin E(T)$, let $C$ be the cycle in $T+e$, $f$ be an edge in $C\cap \delta (v)\setminus \{e\}$, then since $w(f)\ge w(e)$, it follows that $T+e-f$ is a minimum spanning tree containing $e$.

0. Fix a vertex $v$ in $V$.

1. Select an edge $e$ in $\arg {\min }_{e\in \delta (v)}w(e)$.

2. Solve for the graph obtained by contracting $e$ recursively.

Applying the lemma yields that the selected edges form a minimum spanning tree.

This algorithm solves the problem in $\mathcal{O}(|V{|}^2+|E|)$ time and $\mathcal{O}(|E|)$ space.

int prim(int n, int m, const std::vector<int> &u, const std::vector<int> &v, const std::vector<int> &w) {
	std::vector<std::vector<std::pair<int, int>>> adj(n);
	for (int i = 0; i < m; i++) {
		adj[u[i]].emplace_back(v[i], w[i]);
		adj[v[i]].emplace_back(u[i], w[i]);
	}
 
	std::vector dist(n, inf);
	dist[0] = 0;
	std::vector<int> s(n);
	std::iota(s.begin(), s.end(), 0);
	int sum = 0;
 
	while (!s.empty()) {
		int u = std::ranges::min(s, std::less(), [&](int u) -> int {
			return dist[u];
		});
		std::erase(s, u);
 
		sum += dist[u];
		for (auto [v, w] : adj[u]) {
			dist[v] = std::min(dist[v], w);
		}
	}
 
	return sum;
}

Algorithm 1

Based on Algorithm 0, using a Binary Heap to maintain the adjacency list of $v$ yields an algorithm that solves the problem in $\mathcal{O}(|E|\log |E|)$ time and $\mathcal{O}(|E|)$ space.

int prim(int n, int m, const std::vector<int> &u, const std::vector<int> &v, const std::vector<int> &w) {
	std::vector<std::vector<std::pair<int, int>>> adj(n);
	for (int i = 0; i < m; i++) {
		adj[u[i]].emplace_back(v[i], w[i]);
		adj[v[i]].emplace_back(u[i], w[i]);
	}
 
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> q;
	q.emplace(0, 0);
	std::vector vis(n, false);
	int sum = 0;
 
	while (!q.empty()) {
		auto [d, u] = q.top();
		q.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = true;
 
		sum += d;
		for (auto [v, w] : adj[u]) {
			q.emplace(w, v);
		}
	}
 
	return sum;
}