Assignment 3: Optimization of a City Transportation Network (MST)

Overview

This project applies Prim’s and Kruskal’s algorithms to find the Minimum Spanning Tree (MST) for a city transportation network, minimizing total road construction cost.

Features

• JSON input/output
• Prim’s and Kruskal’s algorithms
• Operation and time tracking
• Automated JUnit tests
• CSV and DOCX report

Results Summary

Graph	Prim Cost	Kruskal Cost	Prim Ops	Kruskal Ops	Prim Time (ms)	Kruskal Time (ms)
1	11	11	24	27	0.07	14.50
2	30	30	117	60	0.09	0.16
3	105	105	576	143	0.21	0.13

Conclusion

Both algorithms give identical MST costs.
Kruskal performs better on sparse graphs, Prim on dense ones.

---

Author: Kuan Akerke