Comparative Performance Analysis of Kruskal and Prim MST Algorithms

Abstract
With the increased growth of large-scale networks and
advancements in GIS applications, the use of the minimal
spanning trees has become equally important. The minimal
spanning tree for a given graph is a subgraph whose weight is
minimal, and can be obtained using classical algorithms such
and Kruskal and Prim’s algorithm. Several studies have
focused on improvements made on either Prims or Kruskal
algorithm but very few have analyzed the complexities of these
algorithms. In this study, we investigated the computational
speed complexities of both algorithms to provide an informed
report on which MST algorithm is computationally superior.
Road network datasets comprising 82, 309, 1899, 4039, 6105
and 21048 nodes in succession have been used to simulate both
algorithms, and results showed that Kruskal’s algorithm
performed better than Prim’s algorithm in terms of
computational speed.
Keywords: Minimal spanning trees, Kruskal, Prim,
Performance Analysis, Complexity
I. INTRODUCTION
Algorithmic complexity is concerned with how fast or slow
algorithms perform. Complexity analysis is a tool that allows
us to explain how an algorithm behaves as the input grows
larger. It also helps us analyze the behavior of an algorithm
when the input changes. In order to analyze the complexities of
an algorithm, the algorithm must be implemented and then its
results analyzed. The minimal spanning tree (MST) is a well
known combinatorial optimization problem that has significant
applications in graph theory, with diverse algorithms proposed
to solve it. A minimal spanning tree is a subgraph of a graph
whose weights are minimal. Kruskal and Prim algorithms are
classical algorithms used to provide the optimal MST; Optimal,
based on time or the cost of paths, depending on which is
required. For a graph with v vertices and e edges, both
algorithms run in O (e log n) time, although, Prim’s relies on a
priority queue that supports priority modification while
Kruskal’s relies on a disjoint-set that supports find/union
operations [1]. Suppose a hospital ambulance is to deliver
pharmaceutical drugs to all hospitals in vicinity and the driver
must take these drugs to every hospital exactly once during the
trip. He/she must start from a hospital and end up in a
destination with a minimum total distance covered. In order to
determine the fastest route between hospitals, a minimal
spanning tree is required. Selecting the best route from a
number of alternatives is a problem often encountered. Such a
problem can be modelled as a graph problem. Kruskal and
Prim’s algorithm are popular algorithms for constructing
minimal spanning trees and they have both been used and
modified extensively [2,3,4,5,6,7]. The minimum spanning tree
problem arises in many applications, such as in clustering
problems, image processing and road network transportation
problems [8]. A very unique illustration of MST’s is greedy
algorithms, which always deliver an optimal solution, and use
clever data structures where necessary to make it work
efficiently. A less obvious application is that the minimum
spanning tree can be used to approximately solve the traveling
salesman problem.
In this study, Kruskal and Prim algorithms have been
implemented on a road network graph of major hospitals in
Ibadan, Oyo state, and the computational speed performance of
both algorithms were documented. Different road network
datasets have been used to simulate both algorithms to show the
computational speed superiority of these algorithms.
II. RELATED WORK
[2] compared the performance of Prim and Kruskal’s algorithm
on the Shanghai and Shenzhen 300 index daily stock exchange
data between 2005 and 2007, that is, they compared the
performance of both MST algorithms in constructing the super
metric space of the sample stocks within this period.
Comparison of the space complexity of both algorithms
showed that Kruskal’s algorithm was superior with an input
data less than 100, whereas the time complexity of prims
algorithm was superior to Kruskal’s with an input data size
greater than 100 but had little difference when a data size less
than 100 was used. [9] designed an optimal route for the water
supply system in the Kwahu South District of Ghana using
Prim's algorithm. The map used consisted of 12 nodes and the
distances between the towns were the weights of the graph. It
was seen from the results that the total cost of pipeline
construction was significantly reduced when the MST was used.
[10] also applied the Prims algorithm in designing an optimized
LAN network for Chuka University, Kenya. The algorithm was
used to determine the shortest length of cables to directly link
a set of network nodes supposing all buildings in the university
are connected. The graph used consisted of 11 nodes and the
distance between the buildings were the weights of the graph.
The result showed that the Prims algorithm produced a route
with minimal distance and therefore optimizes the installation

    Date: 2026-08-12 00:00:00.000000