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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the core idea of Kruskal's algorithm

What is the main principle behind Kruskal's algorithm when building a minimum spanning tree?

A Start from a single node and add the cheapest edge connecting to a new node repeatedly

B Add edges in order of increasing weight, skipping those that form a cycle

C Add all edges first, then remove the heaviest edges until no cycles remain

D Randomly add edges until all nodes are connected

💡 Hint

Think about how the algorithm avoids cycles while choosing edges.

Kruskal's algorithm sorts edges by weight and adds them one by one, only if they don't create a cycle. This ensures the tree remains minimal and connected.

🔍 Analysis

intermediate

Detecting cycles in Kruskal's algorithm

Which data structure is commonly used in Kruskal's algorithm to efficiently detect cycles when adding edges?

A Priority Queue

B Queue

C Stack

D Disjoint Set (Union-Find)

💡 Hint

It helps keep track of which nodes belong to the same connected component.

The Disjoint Set or Union-Find data structure helps quickly check if two nodes are already connected, preventing cycles.

🚀 Application

advanced

Output of Kruskal's algorithm on a weighted graph

Given the following edges with weights: (A-B:1), (B-C:4), (A-C:3), (C-D:2), (B-D:5), what edges will Kruskal's algorithm select for the minimum spanning tree?

A (A-B), (C-D), (B-D)

B (A-B), (C-D), (B-C)

C (A-B), (C-D), (A-C)

D (A-C), (C-D), (B-D)

💡 Hint

Sort edges by weight and add them if they don't form a cycle.

Edges sorted by weight: (A-B:1), (C-D:2), (A-C:3), (B-C:4), (B-D:5). Adding (A-B), (C-D), and (A-C) connects all nodes without cycles and minimal total weight.

❓ Reasoning

advanced

Why Kruskal's algorithm sorts edges first

Why does Kruskal's algorithm sort all edges by weight before processing them?

A To ensure the algorithm always picks the smallest available edge to build the MST

B To group edges by their connected nodes

C To speed up cycle detection

D To remove duplicate edges before processing

💡 Hint

Think about how the algorithm guarantees minimal total weight.

Sorting edges by weight ensures the algorithm always considers the smallest edges first, which is essential to build a minimum spanning tree with the least total weight.

❓ Comparison

expert

Comparing Kruskal's and Prim's algorithms

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

A Kruskal's algorithm works better on sparse graphs, while Prim's is more efficient on dense graphs

B Prim's algorithm requires sorting all edges first, Kruskal's does not

C Kruskal's algorithm starts from a single node, Prim's adds edges globally

D Both algorithms always produce different minimum spanning trees

💡 Hint

Consider how each algorithm processes edges and nodes.

Kruskal's algorithm sorts edges and is efficient for sparse graphs with fewer edges. Prim's algorithm grows the MST from a starting node and is often more efficient for dense graphs.