Workspace

Problem workspace

3 day streakD

Prim’s Algorithm

MediumGraphsSpanning trees

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.

Undirected · 6 vertices · 7 edgesA = 0, B = 1, …
Weighted graphUndirected graph with 6 vertices. Start a new tree at A. The priority queue contains edges leaving the growing tree. Restart at any unvisited vertex to handle disconnected graphs. The edge list and state table below provide the graph in text.4121831Aset 1Bset 2Cset 3Dset 4Eset 5Fset 6
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Component representative
ABCDEF
ABCDEF
Step 01 / 10

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 A

Forest

Total weight: 06 component(s)
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.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap