Minimum Spanning Tree Prim's Algorithm in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the MST set in Prim's algorithm.

DSA Python

mstSet = [False] * [1]

Drag options to blanks, or click blank then click option'

Alen(graph)

B0

Crange(len(graph))

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using the graph object directly instead of its length.

Initializing with 0 instead of False.

We create a list of False values with length equal to the number of vertices in the graph to track which vertices are included in the MST.

2fill in blank

medium

Complete the code to find the vertex with the minimum key value not yet included in MST.

DSA Python

for v in range(V):
    if key[v] < min_key and mstSet[[1]] == False:
        min_key = key[v]
        min_index = v

Drag options to blanks, or click blank then click option'

Akey[v]

Bmin_index

Cv

DV

Attempts:

3 left

💡 Hint

Common Mistakes

Using min_index instead of v inside mstSet.

Using key[v] as index.

We check if the vertex v is not yet included in MST by checking mstSet[v].

3fill in blank

hard

Fix the error in updating the key values for adjacent vertices in Prim's algorithm.

DSA Python

for v in range(V):
    if graph[u][v] and mstSet[v] == False and graph[u][v] < [1][v]:
        key[v] = graph[u][v]
        parent[v] = u

Drag options to blanks, or click blank then click option'

Agraph

Bparent

CmstSet

Dkey

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with parent array instead of key array.

Using graph or mstSet incorrectly in comparison.

We compare the edge weight graph[u][v] with the current key value for vertex v to update it if smaller.

4fill in blank

hard

Fill both blanks to correctly initialize the key and parent arrays before starting Prim's algorithm.

DSA Python

key = [[1]] * V
parent = [[2]] * V

Drag options to blanks, or click blank then click option'

Afloat('inf')

BNone

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for key initialization instead of infinity.

Using None for parent instead of -1.

We initialize key values to infinity to represent unknown minimum weights, and parent to -1 to indicate no parent assigned yet.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that builds the MST result with vertex and its parent.

DSA Python

mst_result = { [1]: [2] for [3] in range(1, V) }

Drag options to blanks, or click blank then click option'

Aparent[v]

Bv

Dkey[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping keys and values in the dictionary.

Using key[v] instead of parent[v] as value.

We iterate over vertices v from 1 to V-1, mapping each vertex v to its parent parent[v] in the MST result dictionary.

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