Minimum spanning tree (Prim's) in Data Structures Theory - Full Explanation

Introduction

Imagine you want to connect several cities with roads so that all cities are reachable, but you want to spend the least amount of money building these roads. Finding the cheapest way to connect all points without any loops is the problem that minimum spanning trees solve.

Explanation

Graph and Spanning Tree

A graph is a collection of points called vertices connected by lines called edges. A spanning tree is a subset of these edges that connects all vertices without forming any loops. It ensures every point is reachable from any other point.

A spanning tree connects all points with no cycles.

Minimum Spanning Tree (MST)

Among all possible spanning trees, the minimum spanning tree is the one where the total cost or weight of the edges is as small as possible. This means it uses the cheapest connections to link all points.

MST is the cheapest way to connect all points without loops.

Prim's Algorithm Overview

Prim's algorithm builds the MST by starting from any vertex and growing the tree one edge at a time. At each step, it adds the cheapest edge that connects a new vertex to the growing tree until all vertices are included.

Prim's grows the MST by adding the cheapest edge to new vertices step-by-step.

How Prim's Algorithm Works

Begin with a single vertex and mark it as part of the MST. Look at all edges from this vertex and pick the one with the smallest weight that connects to a vertex not yet in the MST. Add that vertex and edge to the MST. Repeat this process until all vertices are included.

Prim's repeatedly adds the lowest-cost edge connecting the MST to a new vertex.

Data Structures Used

Prim's algorithm often uses a priority queue to efficiently select the next smallest edge. It keeps track of which vertices are in the MST and updates the queue with edges leading to vertices not yet included.

A priority queue helps Prim's quickly find the cheapest edge to add.

Real World Analogy

Imagine building a network of water pipes to connect several houses. You start from one house and always lay the shortest pipe to a new house not yet connected, making sure you don't create loops. This way, you use the least amount of pipe to connect all houses.

Graph and Spanning Tree → Houses as points and pipes as connections between them

Minimum Spanning Tree (MST) → The cheapest way to connect all houses with pipes without any loops

Prim's Algorithm Overview → Starting from one house and adding the shortest pipe to a new house each time

How Prim's Algorithm Works → Choosing the shortest pipe available that connects to a house not yet connected

Data Structures Used → Using a priority queue of shortest pipes to decide which pipe to lay next

Diagram

Diagram

┌───────────────┐
│ Start at any  │
│ vertex (A)    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Select edge   │
│ with smallest │
│ weight to new │
│ vertex       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Add vertex and│
│ edge to MST   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Repeat until  │
│ all vertices  │
│ included      │
└───────────────┘

Flowchart showing Prim's algorithm steps from starting vertex to building the MST by adding edges.

Key Facts

Graph → A set of points connected by lines called edges.

Spanning Tree → A subset of edges connecting all vertices without any cycles.

Minimum Spanning Tree (MST) → A spanning tree with the smallest total edge weight.

Prim's Algorithm → An algorithm that builds the MST by adding the cheapest edge connecting new vertices.

Priority Queue → A data structure that efficiently selects the smallest element.

Code Example

Data Structures Theory

import heapq

def prim_mst(graph, start=0):
    mst = []
    visited = set([start])
    edges = [(cost, start, to) for to, cost in graph[start]]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            for to_next, cost_next in graph[to]:
                if to_next not in visited:
                    heapq.heappush(edges, (cost_next, to, to_next))
    return mst

# Example graph as adjacency list: vertex -> list of (neighbor, cost)
graph = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 3), (3, 8), (4, 5)],
    2: [(1, 3), (4, 7)],
    3: [(0, 6), (1, 8), (4, 9)],
    4: [(1, 5), (2, 7), (3, 9)]
}

mst = prim_mst(graph)
for edge in mst:
    print(edge)

Common Confusions

Believing Prim's algorithm can start from any vertex but must always pick edges connected only to the first vertex.

Believing Prim's algorithm can start from any vertex but must always pick edges connected only to the first vertex. Prim's algorithm starts from any vertex but expands by adding the cheapest edge connecting any vertex already in the MST to a new vertex, not just edges from the starting vertex.

Thinking the MST includes all edges in the graph.

Thinking the MST includes all edges in the graph. The MST includes only enough edges to connect all vertices without cycles, so it has fewer edges than the full graph.

Summary

Minimum spanning trees connect all points with the least total cost and no loops.

Prim's algorithm builds the MST by starting from one vertex and adding the cheapest edge to new vertices step-by-step.

Using a priority queue helps Prim's algorithm efficiently find the next edge to add.

Practice

1. What is the main goal of Prim's algorithm in graph theory?

easy

A. To find the minimum spanning tree connecting all vertices with the least total edge weight

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To sort vertices based on their degree

Solution

1. Step 1: Understand Prim's algorithm purpose

   Prim's algorithm builds a tree that connects all vertices with the minimum sum of edge weights.

2. Step 2: Compare with other graph problems

   Unlike shortest path or cycle detection, Prim's focuses on spanning all vertices with minimal total edge cost.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with the least total edge weight -> Option A

4. Quick Check:

   Prim's algorithm = Minimum spanning tree [OK]

Hint: Prim's always finds the cheapest tree connecting all points [OK]

Common Mistakes:

• Confusing minimum spanning tree with shortest path
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which data structure is commonly used in Prim's algorithm to select the next edge with the smallest weight?

easy

A. Priority queue (min-heap)

B. Stack

C. Queue

D. Hash table

Solution

1. Step 1: Identify how Prim's picks edges

   Prim's algorithm always picks the edge with the smallest weight connecting the tree to a new vertex.

2. Step 2: Choose the right data structure

   A priority queue (min-heap) efficiently retrieves the smallest edge weight at each step.

3. Final Answer:

   Priority queue (min-heap) -> Option A

4. Quick Check:

   Smallest edge selection = Priority queue [OK]

Hint: Use a min-heap to always pick the cheapest edge next [OK]

Common Mistakes:

• Using stack or queue which don't sort by weight
• Confusing hash table with priority queue
• Ignoring edge weights in selection

3. Consider the following weighted graph edges:
A-B: 2, A-C: 3, B-C: 1, B-D: 4, C-D: 5
Using Prim's algorithm starting from vertex A, what is the total weight of the minimum spanning tree?

medium

A. 5

B. 8

C. 7

D. 6

Solution

1. Step 1: Start from vertex A and pick smallest edge

   Edges from A: A-B(2), A-C(3). Pick A-B with weight 2.

2. Step 2: Add next smallest edge connecting new vertices

   From B and A, edges are B-C(1), B-D(4), A-C(3). Pick B-C with weight 1.

3. Step 3: Add next smallest edge to connect remaining vertex D

   Edges from B, C, A to D: B-D(4), C-D(5). Pick B-D with weight 4.

4. Step 4: Calculate total weight

   Total = 2 + 1 + 4 = 7.

5. Final Answer:

   7 -> Option C

6. Quick Check:

   Sum edges 2+1+4 = 7 [OK]

Hint: Add edges with smallest weight connecting new vertices [OK]

Common Mistakes:

• Choosing edges without checking if vertex is already included
• Adding edges that form cycles
• Forgetting to sum all chosen edges

4. In the following code snippet for Prim's algorithm, what is the error?

graph = { 'A': {'B': 2, 'C': 3}, 'B': {'A': 2, 'C': 1, 'D': 4}, 'C': {'A': 3, 'B': 1, 'D': 5}, 'D': {'B': 4, 'C': 5} }
visited = set()
keys = {v: float('inf') for v in graph}
keys['A'] = 0
while len(visited) < len(graph):
    u = min((k for k in keys if k not in visited), key=lambda x: keys[x])
    visited.add(u)
    for v, w in graph[u].items():
        if v not in visited and w < keys[v]:
            keys[v] = w

medium

A. The keys dictionary is not updated correctly

B. The algorithm does not track parent nodes to build the MST

C. The min function call is incorrect

D. The visited set is never updated

Solution

1. Step 1: Analyze the code's MST construction

   The code updates keys but does not store which vertex connects to which, so MST edges are unknown.

2. Step 2: Identify missing MST parent tracking

   Prim's algorithm requires tracking parent nodes to reconstruct the MST edges, which is missing here.

3. Final Answer:

   The algorithm does not track parent nodes to build the MST -> Option B

4. Quick Check:

   Missing parent tracking = MST incomplete [OK]

Hint: Track parents to know MST edges, not just weights [OK]

Common Mistakes:

• Assuming keys alone build MST
• Ignoring parent node tracking
• Thinking visited set is not updated

5. You have a graph with vertices representing cities and edges representing roads with costs. If some roads have zero cost, how does Prim's algorithm handle these edges when building the minimum spanning tree?

hard

A. It always includes zero-cost edges first, possibly creating multiple disconnected trees

B. It causes an error because zero-cost edges are invalid

C. It ignores zero-cost edges because they don't reduce total cost

D. It treats zero-cost edges as the cheapest and includes them first to connect vertices

Solution

1. Step 1: Understand edge weight role in Prim's

   Prim's algorithm always picks the edge with the smallest weight connecting new vertices.

2. Step 2: Consider zero-cost edges

   Zero-cost edges are the cheapest possible, so they will be chosen first to connect vertices without increasing total cost.

3. Step 3: Confirm no errors or ignoring

   Zero-cost edges are valid and included; they do not cause errors or get ignored.

4. Final Answer:

   It treats zero-cost edges as the cheapest and includes them first to connect vertices -> Option D

5. Quick Check:

   Zero-cost edges = chosen first [OK]

Hint: Zero-cost edges are cheapest, so Prim picks them first [OK]

Common Mistakes:

• Thinking zero-cost edges cause errors
• Assuming zero-cost edges are ignored
• Believing zero-cost edges create disconnected trees