---
title: "Write Kruskal's algorithm"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:kruskal-algorithm-write"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/kruskal-algorithm-write
site: BCT Engineering
---

# Write Kruskal's algorithm

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2068 Magh, 2 marks
- Video: [6.6 Kruskals Algorithm for Minimum Spanning Tree- Greedy method | Data structures](https://www.youtube.com/watch?v=EjVHtpWkIho) — Jenny's Lectures CS IT
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/kruskal-algorithm-write
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Write Kruskal's algorithm for minimum spanning tree.

## Short answer

Kruskal's algorithm: initialize each vertex as a separate set, sort edges by weight, and for each edge in order, if its endpoints are in different sets, add it to the MST and union the sets. Time O(E log E).

## Answer

```text
KRUSKAL(G)                       // G = (V, E) connected, weighted, undirected
1. T = empty
2. for each vertex v: MAKE-SET(v)
3. sort E in non-decreasing order of weight
4. for each edge (u, v) in sorted order
5.     if FIND-SET(u) != FIND-SET(v)      // no cycle is formed
6.         T = T + {(u, v)}
7.         UNION(u, v)
8. return T                      // MST with V-1 edges
```
Time complexity: O(E log E), dominated by sorting.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does Kruskal's algorithm do with the edges at the start?
   A. Sorts them in non-decreasing order of weight
   B. Sorts them in decreasing order
   C. Groups them by vertex
   D. Picks them randomly
   Answer: A. Edges are processed from lightest to heaviest. (Key point: Sorting step)

2. How does the algorithm detect that an edge forms a cycle?
   A. FIND-SET(u) equals FIND-SET(v)
   B. The degree of u is 2
   C. UNION fails
   D. The edge weight is largest
   Answer: A. If both ends are already in the same set, adding the edge creates a cycle. (Key point: Cycle check)

3. What is UNION(u, v) used for after accepting an edge?
   A. To reset all sets
   B. To sort the edges again
   C. To delete the edge
   D. To merge the sets of u and v
   Answer: D. After adding the edge, the two components become one. (Key point: Role of UNION)

4. What is Kruskal's time complexity and what dominates it?
   A. O(V^3), dominated by matrix updates
   B. O(E^2), dominated by FIND-SET
   C. O(E log E), dominated by sorting
   D. O(V), dominated by MAKE-SET
   Answer: C. Sorting E edges costs O(E log E). (Key point: Complexity)

## Close variants set in other exams

- [Kruskal's algorithm with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-algorithm-example) — Data Structure and Algorithm, chapter 10, asked 3×

## Related in Data Structure and Algorithm

- [Spanning tree properties; Round Robin MST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aspanning-tree-properties-round-robin) — Data Structure and Algorithm, chapter 10
- [Kruskal's MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-74) — Data Structure and Algorithm, chapter 10, asked 3×
- [Kruskal's MST on graph A to G](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-d) — Data Structure and Algorithm, chapter 10, asked 3×
- [Kruskal's MST on 9-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-f) — Data Structure and Algorithm, chapter 10, asked 3×
- [MST definition; Kruskal's MST on 6-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amst-definition-kruskal-graph-i) — Data Structure and Algorithm, chapter 10
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×

## Related in other subjects

- [Short note: Spanning tree and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aspanning-tree-and-applications) — Discrete Structure, chapter 4
- [Short note: Spanning tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aspanning-tree-short-note) — Discrete Structure, chapter 4, asked 3×
- [Decision tree classifier and Hunt's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Adecision-tree-hunt) — Data Mining, chapter 3