8.
Texas Instruments technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Implementing an algorithm**
Which of the following algorithms is being implemented below?
- Sort all the edges in non-decreasing order of their weight.
- Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
- Repeat step #2 until there are (V-1) edges in the spanning tree.
Show answer & explanation
Answer: B. B) Kruskal's Algorithm
Kruskal's algorithm sorts all graph edges by weight and greedily adds the smallest edge that does not form a cycle until V-1 edges are included.
Step-by-step Derivation:
Step 1: Step 1 sorts edges by weight.
Step 2: Step 2 greedily picks minimum edge and uses Disjoint Set Union (DSU) to check for cycle.
Step 3: Step 3 repeats until spanning tree contains V-1 edges.
Step 4: This is the exact definition of Kruskal's Minimum Spanning Tree algorithm.