Minimum spanning tree (Prim's) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Process

In Prim's algorithm for finding a minimum spanning tree (MST), what is the main criterion for selecting the next edge to add to the growing MST?

A Choose the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST

B Choose the edge with the largest weight that connects any two vertices in the graph

C Choose any edge that connects two vertices already in the MST

D Choose the edge with the smallest weight that connects two vertices outside the MST

💡 Hint

Think about how Prim's algorithm grows the tree step by step.

Prim's algorithm always adds the smallest edge that connects the current MST to a new vertex outside it, ensuring the tree grows with minimum total weight.

📋 Factual

intermediate

Prim's Algorithm Starting Point

Which of the following statements about the starting point of Prim's algorithm is true?

A Prim's algorithm can start from any vertex in the graph

B Prim's algorithm starts from the vertex connected to the edge with the largest weight

C Prim's algorithm starts from the vertex with the highest degree

D Prim's algorithm must start from the vertex with the smallest label

💡 Hint

Consider if the choice of starting vertex affects the final MST.

Prim's algorithm can start from any vertex; the MST found will have the same total weight regardless of the starting point in a connected graph.

🔍 Analysis

advanced

Prim's Algorithm Edge Selection Sequence

Given the following weighted graph edges and starting vertex A, what is the correct order of edges added by Prim's algorithm?

A-B: 2
A-C: 3
B-C: 1
B-D: 4
C-D: 5

A 2,4,1,3

B 2,1,3,4

C 2,1,4,3

D 1,2,3,4

💡 Hint

Remember Prim's algorithm always picks the smallest edge connecting the MST to a new vertex.

Starting at A, the edges chosen in order are A-B (2), B-C (1), B-D (4), and A-C (3) is not chosen because C is already connected.

❓ Comparison

advanced

Prim's vs Kruskal's Algorithm

Which of the following statements correctly compares Prim's and Kruskal's algorithms for finding a minimum spanning tree?

A Kruskal's algorithm requires the graph to be connected, but Prim's algorithm does not

B Kruskal's algorithm only works on directed graphs, while Prim's works on undirected graphs

C Prim's algorithm always produces a different MST than Kruskal's algorithm for the same graph

D Prim's algorithm grows the MST by adding edges connected to the current tree, while Kruskal's algorithm adds edges in order of increasing weight regardless of connectivity

💡 Hint

Think about how each algorithm selects edges and builds the MST.

Prim's algorithm grows the MST from a starting vertex by adding the smallest edge connecting to new vertices. Kruskal's algorithm sorts all edges by weight and adds them if they don't form a cycle, regardless of connectivity.

❓ Reasoning

expert

Effect of Negative Edge Weights on Prim's Algorithm

Consider a connected undirected graph with some negative edge weights. What will be the effect of these negative weights on the minimum spanning tree found by Prim's algorithm?

A Prim's algorithm will ignore negative edges and only use positive edges

B Prim's algorithm cannot handle negative edge weights and will produce incorrect results

C Prim's algorithm will still find a valid minimum spanning tree including negative edges if they reduce total weight

D Prim's algorithm will fail with an error when encountering negative edge weights

💡 Hint

Think about how Prim's algorithm chooses edges based on weight, regardless of sign.

Prim's algorithm works with any edge weights, including negative ones, because it always picks the smallest edge connecting the MST to a new vertex. Negative edges can be included if they help minimize total weight.

Practice

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

easy

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

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort vertices based on their degree

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree that connects all vertices with the minimum sum of edge weights.

2. Step 2: Compare with other graph problems

   Unlike shortest path or cycle detection, Prim's focuses on spanning all vertices with minimal total edge cost.

3. Final Answer:

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

4. Quick Check:

   Prim's algorithm = Minimum spanning tree [OK]

Hint: Prim's always finds the cheapest tree connecting all points [OK]

Common Mistakes:

• Confusing minimum spanning tree with shortest path
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which data structure is commonly used in Prim's algorithm to select the next edge with the smallest weight?

easy

A. Priority queue (min-heap)

B. Stack

C. Queue

D. Hash table

Solution

1. Step 1: Identify how Prim's picks edges

   Prim's algorithm always picks the edge with the smallest weight connecting the tree to a new vertex.

2. Step 2: Choose the right data structure

   A priority queue (min-heap) efficiently retrieves the smallest edge weight at each step.

3. Final Answer:

   Priority queue (min-heap) -> Option A

4. Quick Check:

   Smallest edge selection = Priority queue [OK]

Hint: Use a min-heap to always pick the cheapest edge next [OK]

Common Mistakes:

• Using stack or queue which don't sort by weight
• Confusing hash table with priority queue
• Ignoring edge weights in selection

3. Consider the following weighted graph edges:
A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-D: 5
Using Prim's algorithm starting from vertex A, what is the total weight of the minimum spanning tree?

medium

A. 5

B. 8

C. 7

D. 6

Solution

1. Step 1: Start from vertex A and pick smallest edge

   Edges from A: A-B(2), A-C(3). Pick A-B with weight 2.

2. Step 2: Add next smallest edge connecting new vertices

   From B and A, edges are B-C(1), B-D(4), A-C(3). Pick B-C with weight 1.

3. Step 3: Add next smallest edge to connect remaining vertex D

   Edges from B, C, A to D: B-D(4), C-D(5). Pick B-D with weight 4.

4. Step 4: Calculate total weight

   Total = 2 + 1 + 4 = 7.

5. Final Answer:

   7 -> Option C

6. Quick Check:

   Sum edges 2+1+4 = 7 [OK]

Hint: Add edges with smallest weight connecting new vertices [OK]

Common Mistakes:

• Choosing edges without checking if vertex is already included
• Adding edges that form cycles
• Forgetting to sum all chosen edges

4. In the following code snippet for Prim's algorithm, what is the error?

graph = { 'A': {'B': 2, 'C': 3}, 'B': {'A': 2, 'C': 1, 'D': 4}, 'C': {'A': 3, 'B': 1, 'D': 5}, 'D': {'B': 4, 'C': 5} }
visited = set()
keys = {v: float('inf') for v in graph}
keys['A'] = 0
while len(visited) < len(graph):
    u = min((k for k in keys if k not in visited), key=lambda x: keys[x])
    visited.add(u)
    for v, w in graph[u].items():
        if v not in visited and w < keys[v]:
            keys[v] = w

medium

A. The keys dictionary is not updated correctly

B. The algorithm does not track parent nodes to build the MST

C. The min function call is incorrect

D. The visited set is never updated

Solution

1. Step 1: Analyze the code's MST construction

   The code updates keys but does not store which vertex connects to which, so MST edges are unknown.

2. Step 2: Identify missing MST parent tracking

   Prim's algorithm requires tracking parent nodes to reconstruct the MST edges, which is missing here.

3. Final Answer:

   The algorithm does not track parent nodes to build the MST -> Option B

4. Quick Check:

   Missing parent tracking = MST incomplete [OK]

Hint: Track parents to know MST edges, not just weights [OK]

Common Mistakes:

• Assuming keys alone build MST
• Ignoring parent node tracking
• Thinking visited set is not updated

5. You have a graph with vertices representing cities and edges representing roads with costs. If some roads have zero cost, how does Prim's algorithm handle these edges when building the minimum spanning tree?

hard

A. It always includes zero-cost edges first, possibly creating multiple disconnected trees

B. It causes an error because zero-cost edges are invalid

C. It ignores zero-cost edges because they don't reduce total cost

D. It treats zero-cost edges as the cheapest and includes them first to connect vertices

Solution

1. Step 1: Understand edge weight role in Prim's

   Prim's algorithm always picks the edge with the smallest weight connecting new vertices.

2. Step 2: Consider zero-cost edges

   Zero-cost edges are the cheapest possible, so they will be chosen first to connect vertices without increasing total cost.

3. Step 3: Confirm no errors or ignoring

   Zero-cost edges are valid and included; they do not cause errors or get ignored.

4. Final Answer:

   It treats zero-cost edges as the cheapest and includes them first to connect vertices -> Option D

5. Quick Check:

   Zero-cost edges = chosen first [OK]

Hint: Zero-cost edges are cheapest, so Prim picks them first [OK]

Common Mistakes:

• Thinking zero-cost edges cause errors
• Assuming zero-cost edges are ignored
• Believing zero-cost edges create disconnected trees