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

# Kruskal's algorithm with example

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2072 Asoj, 5 marks; 2073 Bhadra, 4 marks (asked 2 times)
- 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-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Explain Kruskal's algorithm to find minimum spanning tree with suitable example.

## Short answer

Kruskal sorts edges by weight and uses union-find to add edges that don't create cycles. For the example, accepting E-F(1), A-B(2), C-F(3), A-C(6), D-F(9) yields MST edges with minimum cost 21.

## Answer

**Minimum spanning tree (MST):** a spanning tree of a connected, weighted, undirected graph (a tree containing all V vertices and V−1 edges) whose total edge weight is the smallest possible.

**Kruskal's algorithm** is a greedy method: it considers the edges in increasing order of weight and adds an edge to the forest only if it does not form a cycle.

#### Algorithm
```text
KRUSKAL(G)
1. T = empty set
2. make each vertex a separate set (tree)
3. sort all edges in non-decreasing order of weight
4. for each edge (u, v) in sorted order
5.     if FIND(u) != FIND(v)        // different components, no cycle
6.         add (u, v) to T
7.         UNION(u, v)
8.     if T has V-1 edges, stop
9. return T
```
```c
struct edge { int u, v, w; } e[100];
int parent[50];
int find(int x) { while (parent[x] != x) x = parent[x]; return x; }

int kruskal(int V, int E) {
    int total = 0, count = 0;
    sortEdgesByWeight(e, E);                 /* ascending */
    for (int i = 0; i < V; i++) parent[i] = i;
    for (int i = 0; i < E && count < V - 1; i++) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b) {                         /* no cycle */
            parent[a] = b;                    /* union */
            total += e[i].w; count++;
            printf("%d-%d (%d)\n", e[i].u, e[i].v, e[i].w);
        }
    }
    return total;
}
```
**Complexity:** O(E log E), dominated by sorting the edges.

#### Example
Graph: A-B 2, A-C 6, A-F 7, B-D 11, C-F 3, C-E 5, D-F 9, E-F 1 (6 vertices, so the MST has 5 edges).

| Step | Edge | Weight | Decision | Total |
|---|---|---|---|---|
| 1 | E-F | 1 | accept | 1 |
| 2 | A-B | 2 | accept | 3 |
| 3 | C-F | 3 | accept | 6 |
| 4 | C-E | 5 | reject (C, E already joined through F) | 6 |
| 5 | A-C | 6 | accept (joins {A,B} with {C,E,F}) | 12 |
| 6 | A-F | 7 | reject (cycle) | 12 |
| 7 | D-F | 9 | accept | 21 |

Five edges are chosen, so we stop.

**MST edges:** E-F, A-B, C-F, A-C, D-F. **Minimum cost = 21.**

## Check yourself

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

1. How does Kruskal pick edges?
   A. In increasing weight, skipping any that form a cycle
   B. Largest first
   C. Growing from a start vertex
   D. Randomly
   Answer: A. Greedy with cycle check. (Key point: Kruskal idea)

2. How is a cycle detected?
   A. If weights equal
   B. If FIND(u) equals FIND(v)
   C. If degree > 2
   D. If u < v
   Answer: B. Same component means a cycle. (Key point: Cycle check)

3. Why is C-E (5) rejected?
   A. Its weight is too large
   B. E is isolated
   C. C and E are already connected through F
   D. It is a duplicate
   Answer: C. C-F and E-F already join them. (Key point: Rejected edge)

4. What is the MST cost in the example?
   A. 12
   B. 26
   C. 18
   D. 21
   Answer: D. 1+2+3+6+9 = 21. (Key point: Cost)

## Close variants set in other exams

- [Write Kruskal's algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-algorithm-write) — 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