A Study of Kruskal’s Algorithm in Real Road Network of Nagaland


Manoshi Kotoky
Department of Mathematics, School of Basic Sciences, The Assam Kaziranga University, Jorhat, Assam


As we know Graph Theory is used extensively in various fields like engineering, physics, computer science or biology. It is used to prove many mathematical theorems and models. This paper presents the various methods which helps us to find the shortest path between different places. In general, this paper helps us to understand transportation problem and the appropriate method required to tackle the problem. Minimum spanning tree is one such tool which is used to solve the transportation problem. There are different algorithms that are used to define a minimum spanning tree of a graph i.e., Prim’s algorithm, Kruskal’s algorithm, Borvuka’s algorithm, Reverse delete algorithm. The main objective of this paper is to discuss, compare and analyze the formation of Minimum spanning tree using Kruskal’s algorithm taking data in terms of actual distances between different famous tourist places of Nagaland.

October 10, 2022