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.