CodeBlanks Logo Icon CodeBlanks
Login Register

Prim idea

Start at a vertex, add the cheapest edge each step.

Prim idea

Prim's algorithm finds the MST by growing it from a single node. At each step, the node connected with the lowest-weight edge is added to the tree.

While Kruskal sorts edges, Prim grows the tree. Both give the same MST weight but progress differently.

Adjacency matrix

Prim works with an adjacency matrix. graph[i][j] is the edge weight between i and j; if no edge, it is 0. The matrix is symmetric.

All neighbors of a node are visible at a glance. This makes it easy to pick the lowest-weight edge.

Practice init_graph function

Write init_graph(). Return the adjacency matrix. Print it with print(init_graph()).

Starter code

solution.py
def init_graph():
    # Return adjacency matrix

Sample solution

solution.py
def init_graph():
    # Return adjacency matrix
    return [[0, 10, 6, 5], [10, 0, 0, 15], [6, 0, 0, 4], [5, 15, 4, 0]]
print(init_graph())

Expected output

[[0, 10, 6, 5], [10, 0, 0, 15], [6, 0, 0, 4], [5, 15, 4, 0]]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 How does Prim start?

  • From a single node Correct answer
  • From all edges
  • From the longest path
  • From a cycle

Explanation: Prim starts from a single node.

2 Edge weight

Question 
graph[0][1] = ____
Answer 
graph[0][1] = 10

Explanation: 10 is right.

3 Prim idea: match the terms

Term Meaning
graph[0][1] 10
graph[0][2] 6
graph[0][3] 5
graph[2][3] 4

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4