---
title: "Kruskal's MST on graph A to G"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:kruskal-mst-graph-d"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/kruskal-mst-graph-d
site: BCT Engineering
---

# Kruskal's MST on graph A to G

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2073 Magh, 10 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-mst-graph-d
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Explain Kruskal algorithm for finding minimum spanning tree in a graph.
[Figure: undirected weighted graph on vertices A, B, C, D, E, F, G with edges A-B 10, A-F 3, A-G 2, B-G 3, B-C 5, F-G 8, F-E 8, G-E 5, G-C 9, G-D 8, E-D 7, C-D 3]

## Short answer

Kruskal's algorithm sorts edges ascending and uses union-ind. Sorted: A-G2, A-F3, B-G3, C-D3, B-C5, G-E5 accepted. Remaining rejected. MST edges: A-G, A-F, B-G, C-D, B-C, G-E; 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.

#### Application to the given graph
Edges: A-B 10, A-F 3, A-G 2, B-G 3, B-C 5, F-G 8, F-E 8, G-E 5, G-C 9, G-D 8, E-D 7, C-D 3 (7 vertices, so the MST has 6 edges).

Sorted: A-G 2, A-F 3, B-G 3, C-D 3, B-C 5, G-E 5, E-D 7, F-G 8, F-E 8, G-D 8, G-C 9, A-B 10.

| Step | Edge | Weight | Decision | Total |
|---|---|---|---|---|
| 1 | A-G | 2 | accept | 2 |
| 2 | A-F | 3 | accept | 5 |
| 3 | B-G | 3 | accept | 8 |
| 4 | C-D | 3 | accept | 11 |
| 5 | B-C | 5 | accept (joins {A,B,F,G} and {C,D}) | 16 |
| 6 | G-E | 5 | accept (adds E; 6th edge, so stop) | 21 |
| 7 to 12 | remaining | 7, 8, 8, 8, 9, 10 | not needed (each would form a cycle) | 21 |

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

## Check yourself

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

1. Why is Kruskal greedy?
   A. It takes largest edge
   B. It backtracks
   C. It takes the smallest available edge that makes no cycle
   D. It uses recursion
   Answer: C. Local best choice. (Key point: Greedy)

2. Kruskal complexity?
   A. O(V^2)
   B. O(E)
   C. O(V)
   D. O(E log E)
   Answer: D. Dominated by sorting. (Key point: Complexity)

3. Why is E-D (7) rejected?
   A. It would form a cycle
   B. Weight too big
   C. D already visited twice
   D. E isolated
   Answer: A. E and D are already connected. (Key point: Edge E-D)

4. Minimum cost?
   A. 24
   B. 21
   C. 18
   D. 16
   Answer: B. 2+3+3+3+5+5 = 21. (Key point: Cost)

## Close variants set in other exams

- [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 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×

## Related in Data Structure and Algorithm

- [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
- [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
- [Round Robin MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Around-robin-mst-graph-l) — Data Structure and Algorithm, chapter 10
- [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×
- [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 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