Exploring the Maze: A Comparative Study of Prims and Kruskals MST Algorithms
Sakshi Gupta, Archit Mahajan, Sneha A. Shah, Variza Negi · 2024
This research paper offers a comprehensive study of minimum spanning tree (MST) algorithms, mainly focusing on Prims and Kruskals approaches. MST problems holds a fundamental role in combinatorial optimizations, because they help us find the shortest or least time-consuming paths with feasible costs. Due to which they have wide-ranging applications across various domains in real life like communication networks, power grids, transportation systems, piping, and more. The core objective is to find the minimum weight spanning tree, optimizing path selection. To facilitate a comparative study of Prims and Kruskals MST algorithms, we have created a hypothetical scenario utilizing the Traveling Salesman Problem. Our dataset comprises 20 locations (nodes) interconnected by 42 edges representing various distances between locations in kilometers. By applying various MST algorithms, we access and analyse their results and complexities ascertain their efficiency and efficacy under diverse conditions.