The challenge
Connect vertices of an undirected weighted graph with minimum total edge weight and no cycles. If disconnected, return a minimum spanning tree for each component: a minimum spanning forest.
Undirected graph. Negative edge weights are fine. A spanning tree exists only when the graph is connected.
Example
The connected example accepts 5 edges with total weight 8. Isolating E leaves a forest with 4 edges and total weight 7.
Use the walkthrough below to inspect the input and each state change.
See Prim, step by step
Follow the edges. Watch the state change.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| A | B | C | D | E | F |
Start a new tree at A.
The priority queue contains edges leaving the growing tree. Restart at any unvisited vertex to handle disconnected graphs.
heap = edges leaving AForest
View input edges
A — B (4) · A — F (1) · F — B (2) · B — C (1) · F — E (8) · C — D (3) · D — E (1)
Put it into code
Choose the cheapest edge crossing from the current tree to an unvisited vertex.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
from heapq import heappop, heappush
def prim(adj):
# Undirected: store (v, weight) at BOTH endpoints.
seen = [False] * len(adj)
forest, total = [], 0
for root in range(len(adj)):
if seen[root]:
continue
heap = [(0, root, -1)]
while heap:
weight, u, parent = heappop(heap)
if seen[u]:
continue
seen[u] = True
if parent != -1:
forest.append((parent, u, weight))
total += weight
for v, w in adj[u]:
if not seen[v]:
heappush(heap, (w, v, u))
return forest, total # A forest if disconnected.#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using ll = long long;
using Edge = std::tuple<int, int, ll>;
std::pair<std::vector<Edge>, ll> prim(
const std::vector<std::vector<std::pair<int, ll>>>& adj) {
// Store each undirected edge at both endpoints.
int n = static_cast<int>(adj.size());
std::vector<bool> seen(n, false);
std::vector<Edge> forest;
ll total = 0;
using State = std::tuple<ll, int, int>;
for (int root = 0; root < n; ++root) {
if (seen[root]) continue;
std::priority_queue<State, std::vector<State>,
std::greater<State>> heap;
heap.push({0, root, -1});
while (!heap.empty()) {
auto [weight, u, parent] = heap.top();
heap.pop();
if (seen[u]) continue;
seen[u] = true;
if (parent != -1) {
forest.push_back({parent, u, weight});
total += weight;
}
for (auto [v, w] : adj[u])
if (!seen[v]) heap.push({w, v, u});
}
}
return {forest, total};
}