Minimum spanning tree (Prim's) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the starting vertex in Prim's algorithm.

Data Structures Theory

visited = set()
start_vertex = [1]
visited.add(start_vertex)

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

ANone

B0

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from None causes errors because the vertex must be a valid node.

Using -1 or 1 may cause index errors if the graph is zero-indexed.

Prim's algorithm starts from a vertex, often vertex 0 in zero-indexed graphs.

2fill in blank

medium

Complete the code to select the edge with the minimum weight from the priority queue.

Data Structures Theory

while edges:
    weight, vertex = heapq.heappop([1])
    if vertex not in visited:
        break

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

Aqueue

Bvisited

Cgraph

Dedges

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'visited' instead of the priority queue causes errors.

Using 'graph' or 'queue' when those are not the priority queue variable.

Prim's algorithm uses a priority queue (often a heap) named 'edges' to pick the smallest edge.

3fill in blank

hard

Fix the error in the code that adds new edges to the priority queue.

Data Structures Theory

for neighbor, weight in graph[vertex]:
    if neighbor not in visited:
        heapq.heappush(edges, ([1], neighbor))

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

Aweight

Bneighbor

Cvertex

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'neighbor' or 'vertex' as the first tuple element causes incorrect sorting.

Using 'visited' is invalid because it's a set, not a weight.

Edges are pushed with their weight first to maintain the priority queue order by weight.

4fill in blank

hard

Fill both blanks to correctly update the total cost and add the new vertex to visited.

Data Structures Theory

total_cost [1]= weight
visited.[2](vertex)

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

A+

B-

Cadd

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-=' decreases total_cost incorrectly.

Using 'remove' on visited causes errors if vertex is not present.

We add the edge weight to total_cost and add the vertex to the visited set.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that maps vertices to their minimum edge weights.

Data Structures Theory

min_edges = {vertex: [1] for vertex, [2] in graph.items() if [3]

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

Amin(weight for _, weight in graph[vertex])

Bedges

Cvertex in visited

Dvertex not in visited

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'vertex in visited' includes already visited vertices.

Using 'edges' as the second variable in the loop is incorrect; it should be the adjacency list items.

This comprehension finds the minimum edge weight for each vertex not yet visited.