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

# Prim's algorithm with example

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2070 Magh, 5 marks; 2068 Bhadra, 4 marks (asked 2 times)
- Video: [6.5 Prim's Algorithm for Minimum Spanning Tree | Data Structures Tutorials](https://www.youtube.com/watch?v=ZtZaR7EcI5Y) — 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/prim-algorithm-mst
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Explain Prim's algorithm for finding minimum spanning tree along with an example.

## Short answer

Prim grows a tree by adding the cheapest edge connecting a tree vertex to an outside vertex. Starting at A, the chosen edges are A-B(2), A-C(6), C-F(3), F-E(1), F-D(9); MST cost is 21.

## Answer

A **minimum spanning tree (MST)** of a connected weighted undirected graph is a spanning tree with the smallest total edge weight.

**Prim's algorithm** is a greedy method that grows a single tree from a start vertex. At each step it adds the cheapest edge that connects a vertex in the tree to a vertex outside the tree.

#### Algorithm
```text
PRIM(G, start)
1. T = {start};  MST edges = empty
2. while T does not contain all vertices
3.     pick the minimum-weight edge (u, v) with u in T and v not in T
4.     add v to T and edge (u, v) to the MST
```
```c
/* cost[i][j] = weight, INF if no edge */
int prim(int n, int cost[][N]) {
    int total = 0, in[N] = {0};
    in[0] = 1;
    for (int i = 0; i < n - 1; i++) {
        int min = INF, u = -1, v = -1;
        for (int a = 0; a < n; a++) if (in[a])
            for (int b = 0; b < n; b++)
                if (!in[b] && cost[a][b] < min) { min = cost[a][b]; u = a; v = b; }
        in[v] = 1; total += min;
        printf("%d-%d (%d)\n", u, v, min);
    }
    return total;
}
```
Complexity: O(V²) with a matrix (using a key array), O(E log V) with a heap.

#### 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. Start at A.

| Step | Tree T | Candidate edges leaving T | Chosen |
|---|---|---|---|
| 1 | {A} | A-B 2, A-C 6, A-F 7 | A-B (2) |
| 2 | {A,B} | A-C 6, A-F 7, B-D 11 | A-C (6) |
| 3 | {A,B,C} | C-F 3, C-E 5, A-F 7, B-D 11 | C-F (3) |
| 4 | {A,B,C,F} | F-E 1, C-E 5, F-D 9, B-D 11 | F-E (1) |
| 5 | {A,B,C,E,F} | F-D 9, B-D 11 | F-D (9) |

**MST edges:** A-B, A-C, C-F, F-E, F-D. **Minimum cost = 2 + 6 + 3 + 1 + 9 = 21.**

## Check yourself

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

1. How does Prim grow the tree?
   A. Adds cheapest edge anywhere
   B. Adds the cheapest edge from the tree to a vertex outside
   C. Adds largest edge
   D. Sorts all edges first
   Answer: B. One tree from a start vertex. (Key point: Prim idea)

2. After A-B, which edge is chosen?
   A. A-F (7)
   B. B-D (11)
   C. A-C (6)
   D. C-F (3)
   Answer: C. C-F is not yet reachable from the tree. (Key point: Step 2)

3. Minimum cost in the example?
   A. 22
   B. 12
   C. 19
   D. 21
   Answer: D. 2+6+3+1+9 = 21. (Key point: Cost)

4. Complexity with an adjacency matrix?
   A. O(V^2)
   B. O(V)
   C. O(E^2)
   D. O(log V)
   Answer: A. Matrix version. (Key point: Complexity)

## 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
- [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×
- [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2×
- [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×
- [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×

## 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
- [Huffman code tree steps with example](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-code-tree-steps) — Multimedia System, chapter 5, asked 7×