Minimum Spanning Tree Kruskal's Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What edges are included in the Minimum Spanning Tree (MST) after running Kruskal's algorithm on the given graph?

DSA C

Edges with weights: (0-1:4), (0-2:3), (1-2:1), (1-3:2), (2-3:4), (3-4:2), (4-5:6)
Run Kruskal's MST and list edges in MST in order of selection.

A (0-2:3), (1-2:1), (1-3:2), (3-4:2), (4-5:6)

B (1-2:1), (0-1:4), (1-3:2), (3-4:2), (4-5:6)

C (1-3:2), (3-4:2), (0-2:3), (1-2:1), (4-5:6)

D (1-2:1), (1-3:2), (3-4:2), (0-2:3), (4-5:6)

💡 Hint

Sort edges by weight and pick edges that don't form cycles.

Kruskal's algorithm sorts edges by weight and adds edges that connect new vertices without cycles. The edges (1-2:1), (1-3:2), (3-4:2), (0-2:3), and (4-5:6) form the MST.

🧠 Conceptual

intermediate

Why does Kruskal's algorithm use a disjoint set?

What is the main purpose of using a disjoint set (union-find) data structure in Kruskal's algorithm?

A To find the shortest path between two vertices

B To store the graph adjacency list

C To quickly check if adding an edge creates a cycle

D To sort edges by their weights efficiently

💡 Hint

Think about how Kruskal avoids cycles when adding edges.

Disjoint set helps track which vertices are connected. It quickly checks if two vertices belong to the same set, preventing cycles.

🔧 Debug

advanced

Identify the error in this Kruskal's MST code snippet

What error will this code cause when running Kruskal's MST? int parent[5] = {-1, -1, -1, -1, -1}; int find(int x) { if (parent[x] == -1) return x; return find(parent[x]); } void union_set(int x, int y) { int xset = find(x); int yset = find(y); parent[xset] = yset; } // In main, edges are processed and union_set called without checking cycles.

A The code may create cycles because it unions without checking if sets are different

B Stack overflow due to infinite recursion in find function

C Compilation error due to missing return type in union_set

D Array index out of bounds accessing parent array

💡 Hint

Check if union is done only when sets are different.

Union is done without checking if x and y belong to different sets, so cycles can form.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the total weight of the MST after running Kruskal's algorithm on this graph? Edges: (0-1:10), (0-2:6), (0-3:5), (1-3:15), (2-3:4)

A 25

B 19

C 20

D 15

💡 Hint

Add weights of edges selected by Kruskal's MST.

Edges selected: (2-3:4), (0-3:5), (0-1:10). Total weight = 4 + 5 + 10 = 19.

🚀 Application

expert

Kruskal's algorithm on a disconnected graph

If Kruskal's algorithm is run on a graph with two disconnected components, what will be the result?

A It will produce a Minimum Spanning Forest containing MSTs for each component

B It will fail with an error because the graph is not connected

C It will produce a single MST connecting all vertices including disconnected ones

D It will only process the first component and ignore the second

💡 Hint

Think about how MST applies to disconnected graphs.

Kruskal's algorithm produces a Minimum Spanning Forest, which is MSTs for each disconnected component.