Minimum Spanning Trees

This chapter rigorously examines Minimum Spanning Trees (MSTs), fundamental structures in graph theory with extensive applications in network design and optimization. Mastery of MST algorithms, particularly Kruskal's and Prim's, is crucial for the CMI examination, as they frequently appear in problem-solving and theoretical contexts.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Kruskal's Algorithm | | 2 | Prim's Algorithm |

---

We begin with Kruskal's Algorithm.

Part 1: Kruskal's Algorithm

Kruskal's algorithm is a greedy approach used to find a Minimum Spanning Tree (MST) for a connected, undirected graph with weighted edges. We examine its construction process and key properties relevant for CMI graph theory problems.

---

Core Concepts

1. Minimum Spanning Tree (MST)

A spanning tree $T$ of a connected graph $G=(V,E)$ is a subgraph that is a tree and connects all vertices of $G$. A Minimum Spanning Tree (MST) is a spanning tree with the minimum possible total edge weight.

Worked Example:

Consider the graph $G$ below. Identify an MST and its total weight.

```mermaid
graph LR
A -- 1 --> B
A -- 3 --> C
B -- 2 --> C
B -- 5 --> D
C -- 4 --> D
```

Step 1: List all edges and their weights.

> $(A,B): 1$
> $(B,C): 2$
> $(A,C): 3$
> $(C,D): 4$
> $(B,D): 5$

Step 2: Select edges greedily without forming cycles until $|V|-1$ edges are chosen. For $|V|=4$, we need 3 edges.

> 1. Select $(A,B)$ (weight 1). Current edges: $\{(A,B)\}$.
> 2. Select $(B,C)$ (weight 2). Current edges: $\{(A,B), (B,C)\}$.
> 3. Consider $(A,C)$ (weight 3). Adding $(A,C)$ would form cycle $A-B-C-A$. Exclude.
> 4. Select $(C,D)$ (weight 4). Current edges: $\{(A,B), (B,C), (C,D)\}$. This forms a tree with 3 edges.

Answer: The MST edges are $\{(A,B), (B,C), (C,D)\}$ with a total weight of $1+2+4=7$.

:::question type="MCQ" question="Given a connected, undirected graph with 5 vertices and edge weights as $e_1=2, e_2=3, e_3=4, e_4=5, e_5=6, e_6=7$. If an MST has edges $e_1, e_2, e_4, e_x$, what is the maximum possible weight of $e_x$?" options=["4","5","6","7"] answer="7" hint="An MST for a graph with $V$ vertices must have $V-1$ edges. The remaining edge must be selected from the available options to minimize the total weight." solution="A graph with 5 vertices requires an MST with $5-1=4$ edges. The given edges are $e_1=2, e_2=3, e_4=5$. So, we need one more edge $e_x$. The remaining edges are $e_3=4, e_5=6, e_6=7$. To minimize the total weight, we would normally pick the smallest available edge, which is $e_3=4$. However, the question asks for the maximum possible weight of $e_x$. This implies that $e_x$ must be one of the remaining edges that could be part of an MST. If $e_x$ were $e_3=4$, the MST weight would be $2+3+5+4 = 14$. If $e_x$ were $e_5=6$, the MST weight would be $2+3+5+6 = 16$. If $e_x$ were $e_6=7$, the MST weight would be $2+3+5+7 = 17$. Any of these could potentially form an MST depending on the graph structure. Since the question asks for the maximum possible weight of $e_x$, and $e_6=7$ is an available edge that could form a valid MST (if other edges of smaller weight formed cycles), the maximum possible weight is 7.
"
:::

2. Kruskal's Algorithm

Kruskal's algorithm constructs an MST by adding edges in non-decreasing order of weight, provided that adding an edge does not form a cycle with previously selected edges. This greedy strategy guarantees an MST for graphs with distinct edge weights.

Algorithm Steps:

Sort all edges of the graph $G=(V,E)$ in non-decreasing order of their weights.

Initialize an empty set $T$ to store the MST edges and a Disjoint Set Union (DSU) structure where each vertex is in its own set.

Iterate through the sorted edges $(u,v)$ with weight $w(u,v)$:

* If $u$ and $v$ belong to different connected components (checked using DSU's `find` operation), add $(u,v)$ to $T$.
* Merge the connected components of $u$ and $v$ (using DSU's `union` operation).

Stop when $T$ contains $|V|-1$ edges.

Worked Example:

Apply Kruskal's algorithm to find the MST of the following graph:

```mermaid
graph LR
A -- 1 --> B
A -- 7 --> D
B -- 2 --> C
B -- 8 --> E
C -- 3 --> D
C -- 4 --> E
D -- 5 --> E
```

Step 1: List and sort all edges by weight.

> $(A,B): 1$
> $(B,C): 2$
> $(C,D): 3$
> $(C,E): 4$
> $(D,E): 5$
> $(A,D): 7$
> $(B,E): 8$

Step 2: Initialize DSU. Initially, each vertex is in its own set:
$\{A\}, \{B\}, \{C\}, \{D\}, \{E\}$

Step 3: Iterate through sorted edges.

> Edge (A,B), weight 1:
> $\operatorname{find}(A) \ne \operatorname{find}(B)$. Add $(A,B)$ to MST.
> $\operatorname{union}(A,B)$. DSU sets: $\{A,B\}, \{C\}, \{D\}, \{E\}$. MST: $\{(A,B)\}$.

> Edge (B,C), weight 2:
> $\operatorname{find}(B) \ne \operatorname{find}(C)$. Add $(B,C)$ to MST.
> $\operatorname{union}(B,C)$. DSU sets: $\{A,B,C\}, \{D\}, \{E\}$. MST: $\{(A,B), (B,C)\}$.

> Edge (C,D), weight 3:
> $\operatorname{find}(C) \ne \operatorname{find}(D)$. Add $(C,D)$ to MST.
> $\operatorname{union}(C,D)$. DSU sets: $\{A,B,C,D\}, \{E\}$. MST: $\{(A,B), (B,C), (C,D)\}$.

> Edge (C,E), weight 4:
> $\operatorname{find}(C) \ne \operatorname{find}(E)$. Add $(C,E)$ to MST.
> $\operatorname{union}(C,E)$. DSU sets: $\{A,B,C,D,E\}$. MST: $\{(A,B), (B,C), (C,D), (C,E)\}$.

> We have $|V|-1 = 5-1=4$ edges. The algorithm terminates.

Answer: The MST edges are $\{(A,B), (B,C), (C,D), (C,E)\}$ with a total weight of $1+2+3+4=10$.

:::question type="NAT" question="Consider a graph with vertices $V=\{1,2,3,4,5\}$ and edges with weights: $(1,2): 3, (1,3): 5, (2,3): 2, (2,4): 6, (3,4): 4, (3,5): 7, (4,5): 1$. What is the total weight of the MST found by Kruskal's algorithm?" answer="10" hint="Sort edges by weight and add greedily, avoiding cycles. Use a DSU structure conceptually." solution="Step 1: List and sort edges by weight:
> $(4,5): 1$
> $(2,3): 2$
> $(1,2): 3$
> $(3,4): 4$
> $(1,3): 5$
> $(2,4): 6$
> $(3,5): 7$

Step 2: Initialize DSU: $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}$. MST edges: $\emptyset$. Need $5-1=4$ edges.

Step 3: Process edges:

Edge (4,5), weight 1: $\operatorname{find}(4) \ne \operatorname{find}(5)$. Add $(4,5)$ to MST. $\operatorname{union}(4,5)$. Sets: $\{1\}, \{2\}, \{3\}, \{4,5\}$. MST: $\{(4,5)\}$.

Edge (2,3), weight 2: $\operatorname{find}(2) \ne \operatorname{find}(3)$. Add $(2,3)$ to MST. $\operatorname{union}(2,3)$. Sets: $\{1\}, \{2,3\}, \{4,5\}$. MST: $\{(4,5), (2,3)\}$.

Edge (1,2), weight 3: $\operatorname{find}(1) \ne \operatorname{find}(2)$. Add $(1,2)$ to MST. $\operatorname{union}(1,2)$. Sets: $\{1,2,3\}, \{4,5\}$. MST: $\{(4,5), (2,3), (1,2)\}$.

Edge (3,4), weight 4: $\operatorname{find}(3) \ne \operatorname{find}(4)$. Add $(3,4)$ to MST. $\operatorname{union}(3,4)$. Sets: $\{1,2,3,4,5\}$. MST: $\{(4,5), (2,3), (1,2), (3,4)\}$.

We now have 4 edges, which is $|V|-1$. The algorithm terminates.

Step 4: Calculate total weight.
> $1 + 2 + 3 + 4 = 10$.
"
:::

3. Disjoint Set Union (DSU) for Cycle Detection

The Disjoint Set Union (DSU) data structure efficiently manages a collection of disjoint sets. It is crucial for Kruskal's algorithm to determine if adding an edge connects two previously disconnected components or creates a cycle within an existing component.

Worked Example:

Trace the DSU `find` and `union` operations for the graph from the previous Kruskal's example.

Initial state: $P[i]=i$ for all $i \in \{A,B,C,D,E\}$ (parent array representation).

Step 1: Edge (A,B), weight 1.

> $\operatorname{find}(A) = A$, $\operatorname{find}(B) = B$. Since $A \ne B$, add $(A,B)$ to MST.
> $\operatorname{union}(A,B)$: Let's say we set $P[B]=A$.
> Current DSU structure (representatives in bold): $\{\mathbf{A}, B\}, \{\mathbf{C}\}, \{\mathbf{D}\}, \{\mathbf{E}\}$.

Step 2: Edge (B,C), weight 2.

> $\operatorname{find}(B) = \operatorname{find}(A) = A$, $\operatorname{find}(C) = C$. Since $A \ne C$, add $(B,C)$ to MST.
> $\operatorname{union}(A,C)$: Let's say we set $P[C]=A$.
> Current DSU structure: $\{\mathbf{A}, B, C\}, \{\mathbf{D}\}, \{\mathbf{E}\}$.

Step 3: Edge (C,D), weight 3.

> $\operatorname{find}(C) = \operatorname{find}(A) = A$, $\operatorname{find}(D) = D$. Since $A \ne D$, add $(C,D)$ to MST.
> $\operatorname{union}(A,D)$: Let's say we set $P[D]=A$.
> Current DSU structure: $\{\mathbf{A}, B, C, D\}, \{\mathbf{E}\}$.

Step 4: Edge (C,E), weight 4.

> $\operatorname{find}(C) = \operatorname{find}(A) = A$, $\operatorname{find}(E) = E$. Since $A \ne E$, add $(C,E)$ to MST.
> $\operatorname{union}(A,E)$: Let's say we set $P[E]=A$.
> Current DSU structure: $\{\mathbf{A}, B, C, D, E\}$. All vertices are in one set.

Answer: The DSU operations correctly identified when to add an edge and when to merge components, leading to the MST.

:::question type="MCQ" question="In a DSU structure for Kruskal's, if $\operatorname{find}(u) = \operatorname{find}(v)$ for an edge $(u,v)$, what does this imply?" options=["Adding $(u,v)$ will increase the total MST weight.","The edge $(u,v)$ connects two different components.","Adding $(u,v)$ will form a cycle.","The edge $(u,v)$ is the minimum weight edge in a cut."] answer="Adding $(u,v)$ will form a cycle." hint="The `find` operation returns the representative of a set. If two vertices have the same representative, they are already in the same connected component." solution="If $\operatorname{find}(u) = \operatorname{find}(v)$, it means that vertices $u$ and $v$ are already part of the same connected component in the forest built so far by Kruskal's algorithm. Adding the edge $(u,v)$ between two vertices that are already connected would create a cycle. Kruskal's algorithm specifically avoids adding such edges to maintain the tree property."
:::

---

Advanced Applications

1. Properties of MST Edges

Understanding properties related to minimum and maximum weight edges is crucial for conceptual questions.

Worked Example: Minimum Weight Edge ($e_{\min}$)

Let $G$ be a connected graph with distinct edge weights. Let $e_{\min}$ be the edge with the minimum weight in $G$. Does every MST of $G$ contain $e_{\min}$?

Step 1: Consider the edge $e_{\min}=(u,v)$.
> If we remove $e_{\min}$ from $G$, it partitions the vertices into two sets, $S$ and $V \setminus S$, such that $u \in S$ and $v \in V \setminus S$. This forms a cut.

Step 2: Apply the Cut Property.
> Since $e_{\min}$ is the edge with the minimum weight in the entire graph, it must also be the minimum weight edge crossing any cut that separates $u$ and $v$. By the Cut Property, $e_{\min}$ must be included in every MST.

Answer: Yes, every MST must contain $e_{\min}$ if edge weights are distinct.

Worked Example: Maximum Weight Edge ($e_{\max}$)

Let $G$ be a connected graph with distinct edge weights. Let $e_{\max}$ be the edge with the maximum weight in $G$. Does every MST of $G$ exclude $e_{\max}$?

Consider the following graph:
```mermaid
graph LR
A -- 1 --> B
B -- 2 --> C
C -- 10 --> D
```
Here, $e_{\max} = (C,D)$ with weight 10.
The graph has 4 vertices, so an MST needs 3 edges.
The only spanning tree is $\{(A,B), (B,C), (C,D)\}$.
Its total weight is $1+2+10=13$.
In this case, $e_{\max}$ is part of the MST because there is no alternative path to connect $D$ to the rest of the graph with a smaller weight.

Answer: No, an MST does not necessarily exclude $e_{\max}$. It only excludes $e_{\max}$ if $e_{\max}$ is part of a cycle where it is the unique maximum weight edge.

:::question type="MSQ" question="Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{\max}$ be the edge with maximum weight and $e_{\min}$ the edge with minimum weight. What can you say about the following statements?

(I) Every minimum spanning tree of $G$ must contain $e_{\min}$.

(II) Every minimum spanning tree must exclude $e_{\max}$.
" options=["I is True, but II is False","I is False, but II is True","Both I and II are False","Both I and II are True"] answer="I is True, but II is False" hint="Review the Cut Property and consider counterexamples for the maximum weight edge." solution="Statement (I) is True: This is a direct consequence of the Cut Property. If we consider a cut that separates the endpoints of $e_{\min}$, $e_{\min}$ is the unique minimum weight edge crossing this cut (since all weights are distinct). Therefore, $e_{\min}$ must be part of every MST.

Statement (II) is False: While the Cycle Property states that the maximum weight edge on any cycle is not in an MST, $e_{\max}$ (the overall maximum weight edge in the graph) can be part of an MST if it is essential to connect two components. For example, in a path graph like $A-B-C-D$ with weights $w(A,B)=1, w(B,C)=2, w(C,D)=100$, the edge $(C,D)$ is $e_{\max}$ but it must be included in the MST to connect $D$ to the rest of the graph.

Therefore, I is True, but II is False."
:::

2. Kruskal's with Disconnected Graphs

If the input graph is disconnected, Kruskal's algorithm will find a Minimum Spanning Forest (MSF), which is a collection of MSTs, one for each connected component. The algorithm will naturally stop when all edges have been processed or when no more edges can be added without forming a cycle.

Worked Example:

Apply Kruskal's algorithm to the following disconnected graph:

```mermaid
graph LR
A -- 1 --> B
B -- 2 --> C
D -- 3 --> E
E -- 4 --> F
```

Step 1: List and sort edges:
> $(A,B): 1$
> $(B,C): 2$
> $(D,E): 3$
> $(E,F): 4$

Step 2: Initialize DSU: $\{A\}, \{B\}, \{C\}, \{D\}, \{E\}, \{F\}$. MST edges: $\emptyset$.

Step 3: Process edges:

Edge (A,B), weight 1: $\operatorname{find}(A) \ne \operatorname{find}(B)$. Add $(A,B)$. $\operatorname{union}(A,B)$. Sets: $\{A,B\}, \{C\}, \{D\}, \{E\}, \{F\}$. MST: $\{(A,B)\}$.

Edge (B,C), weight 2: $\operatorname{find}(B) \ne \operatorname{find}(C)$. Add $(B,C)$. $\operatorname{union}(B,C)$. Sets: $\{A,B,C\}, \{D\}, \{E\}, \{F\}$. MST: $\{(A,B), (B,C)\}$.

Edge (D,E), weight 3: $\operatorname{find}(D) \ne \operatorname{find}(E)$. Add $(D,E)$. $\operatorname{union}(D,E)$. Sets: $\{A,B,C\}, \{D,E\}, \{F\}$. MST: $\{(A,B), (B,C), (D,E)\}$.

Edge (E,F), weight 4: $\operatorname{find}(E) \ne \operatorname{find}(F)$. Add $(E,F)$. $\operatorname{union}(E,F)$. Sets: $\{A,B,C\}, \{D,E,F\}$. MST: $\{(A,B), (B,C), (D,E), (E,F)\}$.

All edges processed. We have two disjoint sets of connected components.

Answer: Kruskal's produces a Minimum Spanning Forest with edges $\{(A,B), (B,C), (D,E), (E,F)\}$. The total weight is $1+2+3+4=10$. This forest consists of two trees: one spanning $\{A,B,C\}$ and another spanning $\{D,E,F\}$.

:::question type="MCQ" question="If Kruskal's algorithm is applied to a graph that is known to be disconnected, what will be the result?" options=["A single Minimum Spanning Tree covering all vertices.","A set of Minimum Spanning Trees, one for each connected component.","An error, as Kruskal's requires a connected graph.","A graph with cycles, as it cannot form a tree."] answer="A set of Minimum Spanning Trees, one for each connected component." hint="Consider the definition of a spanning tree and what happens when components are isolated." solution="Kruskal's algorithm, by its nature of adding the lowest-weight edges that do not form a cycle, will build a tree within each connected component of the graph. If the graph is disconnected, it will eventually process all edges, and the final set of edges will form a Minimum Spanning Forest (MSF), which is a collection of MSTs, one for each connected component. It will not produce a single MST because not all vertices can be connected."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="NAT" question="A connected graph has 7 vertices and 10 edges. If Kruskal's algorithm is used to find an MST, how many edges will be included in the final MST?" answer="6" hint="The number of edges in an MST is directly related to the number of vertices in a connected graph." solution="For any connected graph with $V$ vertices, a Minimum Spanning Tree (MST) will always contain exactly $V-1$ edges.
Given $V=7$ vertices, the number of edges in the MST will be $7-1=6$."
:::

:::question type="MCQ" question="Which of the following data structures is most commonly used to detect cycles efficiently in Kruskal's algorithm?" options=["Adjacency Matrix","Priority Queue","Disjoint Set Union (DSU)","Hash Table"] answer="Disjoint Set Union (DSU)" hint="Think about how Kruskal's determines if adding an edge creates a cycle by checking component connectivity." solution="Kruskal's algorithm relies on efficiently checking if two vertices belong to the same connected component. If they do, adding an edge between them creates a cycle. The Disjoint Set Union (DSU) data structure is specifically designed for this purpose, providing nearly constant-time amortized operations for finding the representative of a set and merging sets."
:::

:::question type="MCQ" question="Consider a graph with $n$ vertices and $m$ edges. The time complexity of Kruskal's algorithm is generally dominated by:" options=["Sorting the edges","DSU operations","Graph traversal for cycle detection","Initializing the graph structure"] answer="Sorting the edges" hint="Recall the main steps of Kruskal's and their respective complexities." solution="The main steps of Kruskal's algorithm are:

Sorting all edges by weight: This takes $O(E \log E)$ time, where $E$ is the number of edges.

Iterating through sorted edges and performing DSU operations: With path compression and union by rank/size, DSU operations take nearly constant amortized time, $O(E \alpha(V))$, where $\alpha$ is the inverse Ackermann function.

Since $O(E \log E)$ typically dominates $O(E \alpha(V))$, the overall time complexity is $O(E \log E)$. Therefore, sorting the edges is generally the dominant factor."
:::

:::question type="MSQ" question="Which of the following statements about Kruskal's algorithm and MSTs are true for a connected graph with distinct edge weights?" options=["Kruskal's algorithm always finds a unique MST.","If an edge $(u,v)$ is the only path between two components of a partially built MST, it must be included.","Kruskal's algorithm can produce a Minimum Spanning Forest if the graph is connected.","The total weight of the MST is always less than or equal to the sum of all edge weights in the graph."] answer="Kruskal's algorithm always finds a unique MST.,If an edge $(u,v)$ is the only path between two components of a partially built MST, it must be included.,The total weight of the MST is always less than or equal to the sum of all edge weights in the graph." hint="Consider the implications of distinct edge weights and the greedy nature of the algorithm." solution="Kruskal's algorithm always finds a unique MST. True. With distinct edge weights, the choice at each step of Kruskal's algorithm is unique (always pick the smallest available edge that doesn't form a cycle), leading to a unique MST.

If an edge $(u,v)$ is the only path between two components of a partially built MST, it must be included. True. This is a consequence of the Cut Property. If $(u,v)$ is the only path, it means it's the minimum weight edge crossing the cut separating those two components.

Kruskal's algorithm can produce a Minimum Spanning Forest if the graph is connected. False. If the graph is connected, Kruskal's algorithm will always produce a single Minimum Spanning Tree. A forest is produced only if the graph itself is disconnected.

The total weight of the MST is always less than or equal to the sum of all edge weights in the graph. True. An MST uses a subset of the graph's edges. Since edge weights are typically non-negative, the sum of a subset of edge weights cannot exceed the sum of all edge weights."
:::

---

Summary

---

What's Next?

---

---

Part 2: Prim's Algorithm

Prim's algorithm is a greedy method for finding a Minimum Spanning Tree (MST) in a weighted, undirected graph. We use it to connect all vertices in a graph with the minimum possible total edge weight, ensuring no cycles are formed.

---

Core Concepts

1. Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) of a connected, undirected graph with edge weights is a subgraph that is a tree, connects all the vertices, and has the minimum possible total edge weight among all such spanning trees.

Worked Example:

Consider the following graph $G=(V, E)$ with edge weights. We identify an MST by selecting edges that connect all vertices with minimum total weight, avoiding cycles.

A

B

C

D

1

4

5

3

2

Step 1: Identify all vertices and edges with weights.

> Vertices: A, B, C, D
> Edges: (A,B,1), (A,C,4), (B,C,2), (B,D,5), (C,D,3)

Step 2: Select edges to form a spanning tree with minimum total weight.

> We can choose edges (A,B,1), (B,C,2), (C,D,3). These connect all vertices A, B, C, D without forming a cycle.

Step 3: Calculate the total weight of the selected edges.

>

Answer: The MST has a total weight of 6.

:::question type="MCQ" question="Which of the following properties is NOT necessarily true for a Minimum Spanning Tree (MST) of a connected, weighted graph?" options=["It connects all vertices of the graph.","It is a tree, containing no cycles.","It has the minimum possible total edge weight.","It contains the edge with the maximum weight in the graph."] answer="It contains the edge with the maximum weight in the graph." hint="Consider the definition of an MST and its goal." solution="An MST aims to connect all vertices with minimum total weight. While it must connect all vertices and be acyclic, there is no requirement for it to include or exclude any specific edge based on its weight, other than the greedy choices made during construction. It is highly unlikely to contain the maximum weight edge unless it's the only option to connect a component."
:::

---

2. Prim's Algorithm Principles

Prim's algorithm is a greedy algorithm that builds an MST by starting from an arbitrary vertex and iteratively adding the cheapest edge that connects a vertex in the growing MST to a vertex outside it. This process continues until all vertices are included in the MST.

Worked Example:

We apply the initial steps of Prim's algorithm to the graph below, starting from vertex A.

A

B

C

D

1

4

5

3

2

Step 1: Initialize the MST with vertex A.

> Current MST vertices: {A}
> Edges connecting MST to non-MST: (A,B,1), (A,C,4)

Step 2: Select the cheapest edge from the current MST to a non-MST vertex.

> The cheapest edge is (A,B,1). We add B to the MST and (A,B) as an MST edge.

Step 3: Update the set of MST vertices and candidate edges.

> Current MST vertices: {A, B}
> MST Edges: {(A,B,1)}
> Candidate edges from MST to non-MST:
> From A: (A,C,4)
> From B: (B,C,2), (B,D,5)
> Overall candidates: (A,C,4), (B,C,2), (B,D,5)

Answer: After two steps, the MST contains vertices {A, B} and edge (A,B,1). The next edge to be added would be (B,C,2).

:::question type="MCQ" question="Prim's algorithm starts with an arbitrary vertex and grows the MST by adding edges. What is the primary criterion for selecting the next edge to add?" options=["The edge with the smallest weight in the entire graph.","The edge with the largest weight that does not form a cycle.","The edge with the smallest weight that connects a vertex in the MST to a vertex not yet in the MST.","Any edge connected to the starting vertex that has not been visited."] answer="The edge with the smallest weight that connects a vertex in the MST to a vertex not yet in the MST." hint="Recall the greedy principle of Prim's algorithm." solution="Prim's algorithm is a greedy algorithm. At each step, it selects the minimum weight edge that connects any vertex already in the growing MST to any vertex not yet in the MST. This ensures the MST grows optimally."
:::

---

3. Prim's Algorithm Steps with Priority Queue

To efficiently find the minimum weight edge at each step, Prim's algorithm typically uses a min-priority queue. Each vertex not yet in the MST is associated with a `key` value, representing the minimum weight of an edge connecting it to a vertex already in the MST.

Algorithm Steps:

Initialize `$key[v] = \infty$` for all vertices $v$, and `$key[\text{start\_vertex}] = 0$`.

Initialize `$parent[v] = \text{NIL}$` for all vertices $v$.

Create a min-priority queue `Q` and insert all vertices into it.

While `Q` is not empty:

a. Extract the vertex $u$ with the minimum `key` value from `Q`.
b. Add $u$ to the MST.
c. For each neighbor $v$ of $u$:
i. If $v$ is still in `Q` and `$w(u,v) < \operatorname{key}[v]$`, then update `$key[v] = w(u,v)$` and set `$parent[v] = u$`.

Worked Example:

We apply Prim's algorithm to the following graph starting from vertex A.

A

B

C

D

E

7

5

9

8

6

4

Step 1: Initialization.

> $\text{key}$: {A:0, B:$\infty$, C:$\infty$, D:$\infty$, E:$\infty$}
> $\text{parent}$: {A:$\text{NIL}$, B:$\text{NIL}$, C:$\text{NIL}$, D:$\text{NIL}$, E:$\text{NIL}$}
> $\text{Q}$: {A, B, C, D, E}

Step 2: Extract A (key=0). Add A to MST. Update neighbors.

> Extracted: A
> Neighbors of A: B, D
> Update B: `$key[B]=7$`, `$parent[B]=A$`
> Update D: `$key[D]=5$`, `$parent[D]=A$`
> $\text{key}$: {A:0, B:7, C:$\infty$, D:5, E:$\infty$}
> $\text{parent}$: {A:$\text{NIL}$, B:A, C:$\text{NIL}$, D:A, E:$\text{NIL}$}
> $\text{Q}$: {B, C, D, E} (with updated keys)

Step 3: Extract D (key=5). Add D to MST. Update neighbors.

> Extracted: D
> Neighbors of D: A, B, E (A is already in MST)
> Update B: `$w(D,B)=9$`. `key[B]` is 7. $9 \not< 7$, so no update.
> Update E: `$key[E]=4$`, `$parent[E]=D$`
> $\text{key}$: {A:0, B:7, C:$\infty$, D:5, E:4}
> $\text{parent}$: {A:$\text{NIL}$, B:A, C:$\text{NIL}$, D:A, E:D}
> $\text{Q}$: {B, C, E}

Step 4: Extract E (key=4). Add E to MST. Update neighbors.

> Extracted: E
> Neighbors of E: C, D (D is already in MST)
> Update C: `$key[C]=6$`, `$parent[C]=E$`
> $\text{key}$: {A:0, B:7, C:6, D:5, E:4}
> $\text{parent}$: {A:$\text{NIL}$, B:A, C:E, D:A, E:D}
> $\text{Q}$: {B, C}

Step 5: Extract C (key=6). Add C to MST. Update neighbors.

> Extracted: C
> Neighbors of C: B, E (E is already in MST)
> Update B: `$w(C,B)=8$`. `key[B]` is 7. $8 \not< 7$, so no update.
> $\text{key}$: {A:0, B:7, C:6, D:5, E:4}
> $\text{parent}$: {A:$\text{NIL}$, B:A, C:E, D:A, E:D}
> $\text{Q}$: {B}

Step 6: Extract B (key=7). Add B to MST. Update neighbors.

> Extracted: B
> Neighbors of B: A, D, C (A, D, C are already in MST)
> No updates.
> $\text{key}$: {A:0, B:7, C:6, D:5, E:4}
> $\text{parent}$: {A:$\text{NIL}$, B:A, C:E, D:A, E:D}
> $\text{Q}$: {}

Answer: The MST edges are (A,B,7), (A,D,5), (D,E,4), (E,C,6). Total weight = $7+5+4+6 = 22$.

:::question type="NAT" question="Consider a graph with 5 vertices and 7 edges. If Prim's algorithm is implemented with a binary min-heap, what is the time complexity in terms of vertices $V$ and edges $E$?" answer="O((E+V)logV)" hint="Recall the operations involved: extracting minimum and decreasing key, and their costs for a binary heap." solution="Prim's algorithm with a binary min-heap has a time complexity of $O(E \log V)$ or $O((E+V) \log V)$. Each vertex extraction from the priority queue takes $O(\log V)$ time, and there are $V$ such extractions. Each edge relaxation (decrease-key operation) takes $O(\log V)$ time, and there are at most $E$ such operations. Therefore, the total time complexity is $O(V \log V + E \log V) = O((V+E) \log V)$."
:::

---

Advanced Applications

1. Constructing an MST on a Larger Graph

We demonstrate the full application of Prim's algorithm on a slightly larger graph to highlight the iterative nature and priority queue updates.

Consider the following graph:

A

B

C

D

E

F

G

4

2

3

7

1

5

6

8

9

10

11

We start Prim's algorithm from vertex A.

Step 1: Initialization

> $\text{key}$: {A:0, B:$\infty$, C:$\infty$, D:$\infty$, E:$\infty$, F:$\infty$, G:$\infty$}
> $\text{parent}$: {A:$\text{NIL}$, B:$\text{NIL}$, C:$\text{NIL}$, D:$\text{NIL}$, E:$\text{NIL}$, F:$\text{NIL}$, G:$\text{NIL}$}
> $\text{MST\_Edges}$: {}
> $\text{Q}$: {A, B, C, D, E, F, G}

Step 2: Extract A (key=0). Add A to MST. Update neighbors.

> Extracted: A
> Neighbors of A: B, E
> Update B: `$key[B]=4$`, `$parent[B]=A$`
> Update E: `$key[E]=7$`, `$parent[E]=A$`
> $\text{key}$: {A:0, B:4, C:$\infty$, D:$\infty$, E:7, F:$\infty$, G:$\infty$}
> $\text{MST\_Edges}$: {}
> $\text{Q}$: {B, C, D, E, F, G}

Step 3: Extract B (key=4). Add B to MST. Update neighbors.

> Extracted: B
> Neighbors of B: A, C, E, F (A is in MST)
> Add (A,B,4) to $\text{MST\_Edges}$.
> Update C: `$key[C]=2$`, `$parent[C]=B$`
> Update E: `$w(B,E)=1$`. `key[E]` is 7. $1 < 7$, so `$key[E]=1$`, `$parent[E]=B$`
> Update F: `$key[F]=5$`, `$parent[F]=B$`
> $\text{key}$: {A:0, B:4, C:2, D:$\infty$, E:1, F:5, G:$\infty$}
> $\text{MST\_Edges}$: {(A,B,4)}
> $\text{Q}$: {C, D, E, F, G}

Step 4: Extract E (key=1). Add E to MST. Update neighbors.

> Extracted: E
> Neighbors of E: A, B, F (A, B are in MST)
> Add (B,E,1) to $\text{MST\_Edges}$.
> Update F: `$w(E,F)=10$`. `key[F]` is 5. $10 \not< 5$, so no update.
> $\text{key}$: {A:0, B:4, C:2, D:$\infty$, E:1, F:5, G:$\infty$}
> $\text{MST\_Edges}$: {(A,B,4), (B,E,1)}
> $\text{Q}$: {C, D, F, G}

Step 5: Extract C (key=2). Add C to MST. Update neighbors.

> Extracted: C
> Neighbors of C: B, D, F, G (B is in MST)
> Add (B,C,2) to $\text{MST\_Edges}$.
> Update D: `$key[D]=3$`, `$parent[D]=C$`
> Update F: `$w(C,F)=6$`. `key[F]` is 5. $6 \not< 5$, so no update.
> Update G: `$key[G]=8$`, `$parent[G]=C$`
> $\text{key}$: {A:0, B:4, C:2, D:3, E:1, F:5, G:8}
> $\text{MST\_Edges}$: {(A,B,4), (B,E,1), (B,C,2)}
> $\text{Q}$: {D, F, G}

Step 6: Extract D (key=3). Add D to MST. Update neighbors.

> Extracted: D
> Neighbors of D: C, G (C is in MST)
> Add (C,D,3) to $\text{MST\_Edges}$.
> Update G: `$w(D,G)=9$`. `key[G]` is 8. $9 \not< 8$, so no update.
> $\text{key}$: {A:0, B:4, C:2, D:3, E:1, F:5, G:8}
> $\text{MST\_Edges}$: {(A,B,4), (B,E,1), (B,C,2), (C,D,3)}
> $\text{Q}$: {F, G}

Step 7: Extract F (key=5). Add F to MST. Update neighbors.

> Extracted: F
> Neighbors of F: B, E, C, G (B, E, C are in MST)
> Add (B,F,5) to $\text{MST\_Edges}$.
> Update G: `$w(F,G)=11$`. `key[G]` is 8. $11 \not< 8$, so no update.
> $\text{key}$: {A:0, B:4, C:2, D:3, E:1, F:5, G:8}
> $\text{MST\_Edges}$: {(A,B,4), (B,E,1), (B,C,2), (C,D,3), (B,F,5)}
> $\text{Q}$: {G}

Step 8: Extract G (key=8). Add G to MST. Update neighbors.

> Extracted: G
> Neighbors of G: C, D, F (C, D, F are in MST)
> Add (C,G,8) to $\text{MST\_Edges}$.
> $\text{key}$: {A:0, B:4, C:2, D:3, E:1, F:5, G:8}
> $\text{MST\_Edges}$: {(A,B,4), (B,E,1), (B,C,2), (C,D,3), (B,F,5), (C,G,8)}
> $\text{Q}$: {}

Answer: The MST edges are (A,B,4), (B,E,1), (B,C,2), (C,D,3), (B,F,5), (C,G,8).
Total weight = $4+1+2+3+5+8 = 23$.

:::question type="MCQ" question="Which edge would be the LAST one added to the MST by Prim's algorithm when starting from vertex A on the graph in the worked example above?" options=["(C,G) with weight 8","(B,F) with weight 5","(C,D) with weight 3","(E,F) with weight 10"] answer="(C,G) with weight 8" hint="Trace the algorithm carefully and identify the last edge selected based on the parent array or MST edge list." solution="From the detailed trace, the MST edges added in order are: (A,B,4), (B,E,1), (B,C,2), (C,D,3), (B,F,5), (C,G,8). The last edge added is (C,G) with weight 8."
:::

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A connected, weighted graph $G$ has $V$ vertices and $E$ edges. When implementing Prim's algorithm using a min-priority queue based on a binary heap, what is the dominant factor determining its time complexity?" options=["The number of vertices $V$","The number of edges $E$","The product of $V$ and $E$","The logarithm of the number of vertices, $\log V$"] answer="The number of edges E" hint="Consider the operations that occur for each edge and vertex." solution="The time complexity of Prim's with a binary min-heap is $O((V+E)\log V)$. Since graphs typically have $E \ge V-1$, the $E \log V$ term often dominates. While $V \log V$ is present due to vertex extractions, edge relaxations (decrease-key operations) can happen up to $E$ times, each taking $O(\log V)$. Thus, $E$ is the dominant factor in $E \log V$ for connected graphs."
:::

:::question type="NAT" question="Consider a complete graph $K_5$ where all edge weights are distinct positive integers. If Prim's algorithm is run, how many edges will be included in the MST?" answer="4" hint="An MST for a graph with $V$ vertices always contains a specific number of edges." solution="An MST of a connected graph with $V$ vertices always contains exactly $V-1$ edges. For a $K_5$ (5 vertices), the MST will contain $5-1=4$ edges."
:::

:::question type="MSQ" question="Which of the following statements are true regarding Prim's Algorithm?" options=["It can be used to find a shortest path between two specific vertices.","It always produces a unique MST for any given graph.","It is a greedy algorithm.","It works correctly only for graphs with positive edge weights."] answer="It is a greedy algorithm." hint="Review the fundamental properties of Prim's algorithm and MSTs." solution="Prim's algorithm is indeed a greedy algorithm, making locally optimal choices that lead to a globally optimal MST.

• It is designed for MSTs, not shortest paths between two specific vertices (Dijkstra's or Bellman-Ford are for that).


• It does not always produce a unique MST; if there are multiple edges with the same minimum weight that could be chosen, different MSTs with the same total weight can exist.


• It works correctly for graphs with non-negative edge weights. While usually presented with positive weights, zero-weighted edges are fine. Negative edge weights are also generally fine, as long as there are no negative cycles, but Prim's focuses on weights relative to each other, not absolute values. The issue with negative cycles is more relevant to shortest path algorithms."

:::

:::question type="MCQ" question="If a graph is disconnected, and Prim's algorithm is run starting from a vertex in one of its connected components, what will be the result?" options=["It will find an MST for the entire graph by eventually connecting all components.","It will find an MST for the connected component containing the starting vertex.","It will terminate prematurely, indicating an error.","It will enter an infinite loop trying to find a connection." ] answer="It will find an MST for the connected component containing the starting vertex." hint="Prim's algorithm operates within connected structures." solution="Prim's algorithm requires a connected graph to find a spanning tree that includes all vertices. If the graph is disconnected, it will only be able to find an MST for the connected component to which the starting vertex belongs, as there are no edges connecting that component to others."
:::

:::question type="NAT" question="A graph has 6 vertices and 9 edges. If Prim's algorithm is run, and the edges selected for the MST are (A,B,2), (B,C,3), (C,D,1), (D,E,4), (E,F,5), what is the total weight of the MST?" answer="15" hint="Sum the weights of the edges included in the MST." solution="The total weight of the MST is the sum of the weights of all selected edges: $2 + 3 + 1 + 4 + 5 = 15$."
:::

---

Summary

---

What's Next?

Chapter Summary

Chapter Review Questions

:::question type="MCQ" question="Which of the following statements about Kruskal's and Prim's algorithms for finding a Minimum Spanning Tree (MST) is generally true?" options=["Kruskal's algorithm is typically more efficient for dense graphs than Prim's algorithm." , "Prim's algorithm requires the graph to be represented using an adjacency matrix for optimal performance." , "Both algorithms provide a unique MST if all edge weights are distinct." , "Kruskal's algorithm always starts building the MST from a designated source vertex."] answer="Both algorithms provide a unique MST if all edge weights are distinct." hint="Consider the properties of MSTs and the operational differences between the algorithms." solution="Both Kruskal's and Prim's algorithms are correct and will find an MST. If all edge weights are distinct, the MST is unique, and both algorithms will identify it. Kruskal's is often better for sparse graphs due to its edge-sorting nature, while Prim's (especially with a Fibonacci heap) can be more efficient for dense graphs. Prim's does not require an adjacency matrix; a priority queue with an adjacency list is common. Kruskal's does not start from a designated source; it considers edges globally."
:::

:::question type="NAT" question="Consider an undirected, weighted graph with vertices A, B, C, D, E and edges with weights: (A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,D,8), (C,E,10), (D,E,2). What is the total weight of its Minimum Spanning Tree?" answer="10" hint="You can use either Kruskal's or Prim's algorithm. For Kruskal's, sort edges by weight and add them if they don't form a cycle. For Prim's, start from any vertex and grow the tree." solution="Using Kruskal's Algorithm:

Sort edges: (B,C,1), (A,C,2), (D,E,2), (A,B,4), (B,D,5), (C,D,8), (C,E,10).

Add (B,C,1). Components: {A}, {B,C}, {D}, {E}. MST weight = 1.

Add (A,C,2). Components: {A,B,C}, {D}, {E}. MST weight = 1+2 = 3.

Add (D,E,2). Components: {A,B,C}, {D,E}. MST weight = 3+2 = 5.

(A,B,4) connects A and B, which are already in the same component {A,B,C}. Skip.

Add (B,D,5). Components: {A,B,C,D,E}. MST weight = 5+5 = 10.

All 5 vertices are connected with 4 edges. The total weight of the MST is 10."
:::

:::question type="MCQ" question="If an edge $(u,v)$ with weight $w$ is part of an MST of a graph $G$, which of the following must be true?" options=["There is no other path between $u$ and $v$ in $G$ with a total weight less than $w$." , "Removing $(u,v)$ from the MST splits the MST into two components, and $(u,v)$ is the minimum weight edge connecting these two components." , "Every other edge in $G$ has a weight greater than or equal to $w$." , "The cycle formed by adding any other edge to the MST must contain $(u,v)$." ] answer="Removing $(u,v)$ from the MST splits the MST into two components, and $(u,v)$ is the minimum weight edge connecting these two components." hint="Consider the cut property of MSTs." solution="This is a direct application of the cut property of MSTs. If an edge $(u,v)$ is in an MST, then removing it splits the MST into two components. $(u,v)$ must be the minimum weight edge crossing the cut defined by these two components; otherwise, a lighter edge could replace it, leading to a lighter spanning tree, which contradicts the definition of an MST. The other options are incorrect: there could be other paths between $u$ and $v$ with higher total weights, not necessarily lower; other edges in $G$ can have weights less than $w$; and adding another edge to the MST forms a cycle that may or may not contain $(u,v)$."
:::

What's Next?