Assignment 3: Minimum Spanning Tree using Prim’s Algorithm

Overview

This assignment implements Prim’s algorithm using a custom heap-based priority queue to compute the Minimum Spanning Tree (MST) of a weighted undirected graph. The implementation meets the required time complexity of O((|V| + |E|) log |V|).

Objectives

• Implement a heap-based priority queue with support for:
  • heap(keys, n)
  • in_heap(id)
  • is_empty()
  • min_key(), min_id()
  • delete_min()
  • decrease_key(id, new_key)
• Use this heap in Prim's algorithm starting from vertex 1
• Parse an input graph file and output:
  1. Adjacency list
  2. Edges in the MST
  3. Total MST weight

Files

File Name	Description
asn3.py	Python program implementing Prim’s algorithm with heap
asn3.sh	Shell script to run the program using asn3.py
asn3_solution.pdf	Written answers for questions 1 to 6 of the assignment
infile	Input graph file used to test MST algorithm
asn3.pdf	Assignment instructions (for context/reference)

Input Format

The infile contains:

• First line: Integer n representing number of vertices
• Each following line: i j w describing an edge between vertices i and j with weight w

Output Format

The program outputs:

1. Adjacency list for the input graph
2. Edges in the MST in the format (i, j), weight: w, where i is the parent of j
3. Total weight of the MST

How to Run

On any Unix environment:

./asn3 < infile

Alternative Manual Run

python3 asn3.py < infile

Sample Output

Adjacency List:
(1, 2), weight: 28
(1, 3), weight: 15
...

Minimum Spanning Tree:
(1, 2), weight: 28
(2, 4), weight: 10
...

Weight of the Minimum Spanning Tree: 131

License

For academic use only — University of Western Ontario, CS 3340b: Analysis of Algorithms