Minimum Spanning Tree Prim's Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Small Graph

What is the total weight of the minimum spanning tree after running Prim's algorithm starting from node 0 on the given graph?

DSA Python

graph = {
    0: {1: 2, 3: 6},
    1: {0: 2, 2: 3, 3: 8, 4: 5},
    2: {1: 3, 4: 7},
    3: {0: 6, 1: 8, 4: 9},
    4: {1: 5, 2: 7, 3: 9}
}

import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0

    while min_heap:
        weight, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for adj, w in graph[node].items():
            if adj not in visited:
                heapq.heappush(min_heap, (w, adj))
    return total_weight

result = prim(graph, 0)
print(result)

A 18

B 14

C 16

D 20

💡 Hint

Trace the edges chosen by Prim's algorithm starting from node 0 and sum their weights.

Prim's algorithm starts at node 0 and picks edges with the smallest weight connecting to unvisited nodes. The edges chosen are (0-1:2), (1-2:3), (1-4:5), and (0-3:6). Their sum is 2 + 3 + 5 + 6 = 16. However, the edge (3-4:9) is not chosen because 4 is already visited. The total weight is 16.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Behavior

Which of the following statements about Prim's algorithm is correct?

A Prim's algorithm always starts from the node with the smallest value.

B Prim's algorithm grows the minimum spanning tree by adding the smallest edge connecting the tree to a new node.

C Prim's algorithm can only be used on directed graphs.

D Prim's algorithm always produces the maximum spanning tree.

💡 Hint

Think about how Prim's algorithm chooses edges to add to the tree.

Prim's algorithm starts from any node and grows the tree by adding the smallest edge that connects the tree to a new node. It works on undirected graphs and produces a minimum spanning tree, not maximum.

🔧 Debug

advanced

Identify the Error in Prim's Algorithm Implementation

What error will the following Prim's algorithm code produce when run on a connected graph?

DSA Python

def prim_bug(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0

    while min_heap:
        weight, node = min_heap.pop()
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for adj, w in graph[node].items():
            if adj not in visited:
                min_heap.append((w, adj))
    return total_weight

# graph is a dictionary of dictionaries

A The code raises an IndexError due to popping from an empty list.

B The code runs correctly and returns the minimum spanning tree weight.

C The code raises a KeyError when accessing graph[node].

D The code produces an incorrect total weight because it does not use a priority queue.

💡 Hint

Consider how the edges are selected from the min_heap list.

The code uses a list and pops from the end, which does not guarantee the smallest edge is chosen next. This breaks Prim's algorithm logic and results in an incorrect total weight.

❓ Predict Output

advanced

Prim's Algorithm Output on a Disconnected Graph

What will be the output of the following code when Prim's algorithm is run starting from node 0 on a disconnected graph?

DSA Python

graph = {
    0: {1: 4},
    1: {0: 4},
    2: {3: 5},
    3: {2: 5}
}

import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0

    while min_heap:
        weight, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for adj, w in graph.get(node, {}).items():
            if adj not in visited:
                heapq.heappush(min_heap, (w, adj))
    return total_weight

print(prim(graph, 0))

A 4

B 9

C 0

D Raises a KeyError

💡 Hint

Prim's algorithm only visits nodes connected to the start node.

The graph has two disconnected parts: nodes 0-1 and nodes 2-3. Starting from node 0, only nodes 0 and 1 are visited. The edge weight between them is 4, so total weight is 4.

🧠 Conceptual

expert

Time Complexity of Prim's Algorithm with Different Data Structures

Which of the following statements about the time complexity of Prim's algorithm is correct when using a binary heap and adjacency list representation?

A The time complexity is O(E log V) because each edge is pushed and popped from the heap at most once.

B The time complexity is O(V^2) because each vertex is processed once and edges are ignored.

C The time complexity is O(V + E) because the algorithm only visits each vertex and edge once.

D The time complexity is O(E^2) because the heap operations dominate the runtime.

💡 Hint

Consider how many times edges are added to the heap and how heap operations cost.

Using a binary heap and adjacency list, each edge is pushed into the heap at most once, and each heap operation costs O(log V). Thus, total time is O(E log V).

Practice

1. What is the main goal of Prim's algorithm in graph theory?

easy

A. To detect cycles in a graph

B. To find the shortest path between two vertices

C. To find the minimum spanning tree connecting all vertices with the least total edge weight

D. To sort the vertices in topological order

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree connecting all vertices with minimum total edge weight.

2. Step 2: Compare with other graph algorithms

   Shortest path, cycle detection, and topological sort serve different purposes than Prim's.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with the least total edge weight -> Option C

4. Quick Check:

   Prim's algorithm = Minimum Spanning Tree [OK]

Hint: Prim's finds minimum spanning tree, not shortest path [OK]

Common Mistakes:

• Confusing Prim's with Dijkstra's shortest path
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which of the following Python data structures is most suitable to efficiently select the next edge with the smallest weight in Prim's algorithm?

easy

A. List

B. Priority Queue (heapq)

C. Dictionary

D. Queue

Solution

1. Step 1: Identify the need for selecting minimum edge

   Prim's algorithm repeatedly selects the edge with the smallest weight.

2. Step 2: Choose data structure for efficient minimum extraction

   Priority Queue (heapq) allows efficient extraction of the smallest element.

3. Final Answer:

   Priority Queue (heapq) -> Option B

4. Quick Check:

   Minimum edge selection = Priority Queue [OK]

Hint: Use heapq for fast minimum edge extraction [OK]

Common Mistakes:

• Using list and scanning all edges each time
• Using queue which is FIFO, not minimum-based
• Using dictionary which doesn't order by weight

3. What is the output of the following Python code implementing Prim's algorithm on the given graph?

graph = {
  0: [(1, 2), (3, 6)],
  1: [(0, 2), (2, 3), (3, 8), (4, 5)],
  2: [(1, 3), (4, 7)],
  3: [(0, 6), (1, 8), (4, 9)],
  4: [(1, 5), (2, 7), (3, 9)]
}

import heapq

def prim(graph, start=0):
    mst = []
    visited = set([start])
    edges = [(weight, start, to) for to, weight in graph[start]]
    heapq.heapify(edges)

    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, weight))
            for to_next, w in graph[to]:
                if to_next not in visited:
                    heapq.heappush(edges, (w, to, to_next))
    return mst

print(prim(graph))

medium

A. [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]

B. [(0, 3, 6), (3, 4, 9), (1, 4, 5), (1, 2, 3)]

C. [(0, 1, 2), (0, 3, 6), (1, 4, 5), (2, 4, 7)]

D. [(1, 2, 3), (2, 4, 7), (0, 3, 6), (1, 4, 5)]

Solution

1. Step 1: Start from vertex 0 and add edges

   Edges from 0: (0-1,2), (0-3,6). Choose smallest: (0-1,2).

2. Step 2: Add edges from vertex 1 and pick next smallest

   From 1: (1-2,3), (1-3,8), (1-4,5). Next smallest edge overall is (1-2,3).

3. Step 3: Continue adding edges and selecting minimum

   Next edges: (1-4,5), (0-3,6). Choose (1-4,5) then (0-3,6).

4. Final Answer:

   [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)] -> Option A

5. Quick Check:

   Edges chosen in ascending weight order form MST [OK]

Hint: Pick edges by smallest weight connecting new vertices [OK]

Common Mistakes:

• Choosing edges with higher weight first
• Adding edges that create cycles
• Not updating visited vertices correctly

4. The following code snippet for Prim's algorithm has a bug. What is the error?

def prim_bug(graph, start=0):
    mst = []
    visited = set()
    edges = [(0, start, start)]
    while edges:
        weight, frm, to = edges.pop()
        if to not in visited:
            visited.add(to)
            if frm != to:
                mst.append((frm, to, weight))
            for to_next, w in graph[to]:
                if to_next not in visited:
                    edges.append((w, to, to_next))
    return mst

medium

A. The start vertex is never added to visited

B. Visited set is not initialized properly

C. Edges are not added to the list

D. Using list pop() instead of priority queue causes wrong edge selection order

Solution

1. Step 1: Check how edges are selected

   Edges are popped from a list using pop(), which removes the last element, not the smallest weight.

2. Step 2: Understand Prim's requirement for minimum edge selection

   Prim's requires selecting the edge with the smallest weight each time, which needs a priority queue (heap).

3. Final Answer:

   Using list pop() instead of priority queue causes wrong edge selection order -> Option D

4. Quick Check:

   Edge selection order must be by minimum weight [OK]

Hint: Use heapq, not list pop(), to pick minimum edge [OK]

Common Mistakes:

• Using list pop() instead of heapq.heappop()
• Not initializing visited with start vertex
• Appending edges incorrectly

5. Given a weighted undirected graph with vertices 0 to 5 and edges:

0-1: 4, 0-2: 3, 1-2: 1, 1-3: 2, 2-3: 4, 3-4: 2, 4-5: 6

Using Prim's algorithm starting at vertex 0, what is the total weight of the minimum spanning tree?

hard

A. 9

B. 14

C. 10

D. 12

Solution

1. Step 1: Start from vertex 0 and pick smallest edges

   Edges from 0: (0-2,3), (0-1,4). Choose (0-2,3).

2. Step 2: Add edges from visited vertices and pick smallest

   Visited: {0,2}. Edges: (2-1,1), (0-1,4), (2-3,4). Choose (2-1,1).

3. Step 3: Continue adding edges

   Visited: {0,1,2}. Edges: (1-3,2), (0-1,4), (2-3,4). Choose (1-3,2).

4. Step 4: Add edges from 3

   Visited: {0,1,2,3}. Edges: (3-4,2), (2-3,4), (0-1,4). Choose (3-4,2).

5. Step 5: Add edges from 4

   Visited: {0,1,2,3,4}. Edges: (4-5,6), (2-3,4), (0-1,4). Choose (4-5,6).

6. Step 6: Calculate total weight

   Edges chosen: 3 + 1 + 2 + 2 + 6 = 14.

7. Final Answer:

   14 -> Option A

8. Quick Check:

   Sum of MST edges = 14 [OK]

Hint: Add edges by smallest weight connecting new vertices until all included [OK]

Common Mistakes:

• Including edges that form cycles
• Skipping the smallest connecting edge
• Miscounting total weight