Visited set

Mark vertices added to the tree.

Visited set

The picked node is marked visited and its neighbors' keys are updated. If a shorter edge exists, keys[v] decreases.

This is repeated n times; each round one node joins the tree. When all nodes are visited, the MST is complete.

Total computation

Each round, the picked node's keys value is added to the total. This is the weight of the edge joining the tree. The total is the MST weight.

Prim's output matches Kruskal's: a single number. Different progress yields the same result.

Exercise prim function

Write prim(graph). min_key is given; each round pick the lowest node, update neighbors, sum. Print 19 with print(prim(init_graph())).

Show example solution

def init_graph():
    # Return adjacency matrix
    return [[0, 10, 6, 5], [10, 0, 0, 15], [6, 0, 0, 4], [5, 15, 4, 0]]
def min_key(keys, visited):
    # Find unvisited index with smallest keys
    best = float('inf')
    idx = -1
    for i in range(len(keys)):
        if not visited[i] and keys[i] < best:
            best = keys[i]
            idx = i
    return idx
def prim(graph):
    # Find MST weight
    n = len(graph)
    keys = [float('inf')] * n
    keys[0] = 0
    visited = [False] * n
    total = 0
    for _ in range(n):
        u = min_key(keys, visited)
        visited[u] = True
        total += keys[u]
        for v in range(n):
            if graph[u][v] and not visited[v] and graph[u][v] < keys[v]:
                keys[v] = graph[u][v]
    return total
print(prim(init_graph()))

Test yourself

Visited set: match the terms

keys[0]

0
keys[1]

10
keys[2]

6
keys[3]

5
What is Prim's MST weight in the example graph?
- 25
- 15
- 19
- 10
Show answer

19 — 0+5+4+10=19 (same MST).
Accumulation
```
total += keys[____]
```
Show answer
```
total += keys[u]
```

Next lesson: Summary - Prim

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies