Prim's algorithm; MST complexities

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Kruskal's cost? from Lesson 6.2.2
• Cut property? from Lesson 6.2.1
• Binary heap insert and extract cost? from Lesson 0.2.2

1 · The Hook

🎣

Prim's algorithm grows a single tree from a start vertex, always adding the cheapest edge that leaves the tree. It is Kruskal's twin for MSTs and Dijkstra's twin for shortest paths, and GATE asks for the order in which Prim adds vertices.

2 · Predict First

🤔

Prim from A on the six-town graph. Which vertex joins the tree second (after A)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Edges leaving {A}: A–B 4, A–C 2. The cheaper is A–C, so C joins.

Prim's algorithm

key[v] = ∞ for all v; key[start] = 0; tree = {}
while some vertex is outside the tree:
    u = the outside vertex with the smallest key       // cheapest edge leaving the tree
    add u to the tree
    for each neighbour v of u outside the tree:
        if w(u, v) < key[v]: key[v] = w(u, v); parent[v] = u

The tree is always one connected piece; by the cut property (cut = tree vs the rest) every added edge is safe.

Six-town trace from A

Order A, C, B, D, E, F, weight 13 (same MST as Kruskal).

Cost by data structure

4 · Visual

Prim keys (cheapest known edge into the tree), six towns from A

      B    C    D    E    F
A:    4    2    -    -    -      take C (2)
C:    1    *    8   10    -      take B (1)
B:    *    *    5   10    -      take D (5)
D:    *    *    *    2    6      take E (2)
E:    *    *    *    *    3      take F (3)      total 13

5 · Worked Examples

Example 1 Easy

Prim from F on the six-town graph: order of vertices?

Solution

F; E (3); D (2); B (5); C (1); A (2): F, E, D, B, C, A.

Example 2 Medium

For a dense graph with E ≈ V², which Prim implementation is asymptotically faster: array or binary heap?

Solution

Array Θ(V²) vs heap Θ(V² log V): the array.

Example 3 GATE

Prim from A on the six-town graph: weight of the third edge added?

Solution

A–C 2, C–B 1, then B–D 5.

6 · GATE Traps

⚠️

• Prim keeps one tree; Kruskal keeps a forest.
• key[v] is a single edge weight into the tree, not a path length (that is Dijkstra).
• Array version Θ(V²) beats the heap on dense graphs.
• Different start vertices give the same MST weight, different orders.

7 · Memory Hook

🧠

"Prim: one tree, cheapest edge out."

8 · Connect the Dots

Chapter 6.2 is complete. Chapter 6.3 changes one line of Prim, key = path length instead of edge weight, and gets Dijkstra's shortest-path algorithm.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markPrim order

Prim from A on the six-town graph: which vertex is added fourth (A is first)?

• (A) B
• (B) D
• (C) E
• (D) F

Q2NAT2 marksPrim

Prim from F on the six-town graph: weight of the third edge added?

Numerical answer: ________

Q3MCQ1 markArray version

Prim's algorithm with an adjacency matrix and a plain array of keys runs in:

• (A) Θ(E log V)
• (B) Θ(V³)
• (C) Θ(E + V)
• (D) Θ(V²)

Q4NAT1 markPrim weight

MST weight found by Prim from D on the six-town graph?

Numerical answer: ________

Q5MSQ2 marksPrim vs Kruskal

Which are true?

• (A) With distinct weights, both return the same MST.
• (B) Prim's partial solution is always a single tree.
• (C) Both rely on the cut property.
• (D) Kruskal's partial solution is always a single tree.

10 · Rule Card

• Prim: grow one tree; add the outside vertex with the smallest key (cheapest edge in).
• Θ(V²) array (dense graphs); O(E log V) binary heap; O(E + V log V) Fibonacci heap.
• Prim one tree; Kruskal a forest; both via the cut property.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Prim's algorithmkey valuesone growing treePrim cost by priority structurePrim vs Kruskal

12 · Answer Vault