Summary - Prim

Run Prim and print the MST weight in a mini task.

Summary - Prim

In this group you learned Prim, which finds the MST by growing from a single node. Adjacency matrix, min_key and visited set combine into the solution.

Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Exercise mst_total function

Write mst_total(graph). min_key is given; each round pick the lowest node, update neighbors, sum. Print 19 with print(mst_total(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 mst_total(graph):
    # Find total 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(mst_total(init_graph()))

Test yourself

What is the common output of Prim and Kruskal?
- Edge list
- Node order
- Cycle count
- MST weight
Show answer

MST weight — Both return the MST weight.
Visited update
```
visited[____] = True
```
Show answer
```
visited[u] = True
```
Summary - Prim: match the terms

init_graph

Matrix
min_key

Selection
prim

MST
keys

Cost

Next lesson: Dependency order

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies