Analysis between Prims and Kruskal’s Algorithm

Abstract

The project is an analytical comparison between two algorithms that is Prim’s algorithm and Kruskal’s algorithm in MST (minimum spanning tree). Both the algorithms aim to connect all the vertices based on their weight but differ in implementation and approach. Prim’s algorithm is Greedy algorithm which makes the minimum spanning tree according to their incremental weight It starts with one vertex and expands its MST, it always selects smallest edge in MST. Kruskal’s algorithm is also greedy algorithm but its approaches differently. It starts with all the vertices and no edge and it adds edge with one by one according their increasing order of the weight.

Introduction

I. INTRODUCTION

In this paper we have selected topic as a analytical comparison between Prims and Kruskal’s algorithms in MST (Minimum spanning tree). In this paper we will discuss about MST problems solving methods. Base of these method is Spanning tree So the Spanning three is nothing but subgraph of undirected graph which contains all the vertices, edges. The MST (Minimum Spanning Tree) is same as spanning tree but it contains the minimum number of edge weight. Here we will be comparing two algorithms Prims and Kruskal algorithms we are using python as a programming language to solve the problem

A. Brief of Algorithms

Kruskal’s Algorithms: It is a Greedy method which connects all the vertices without forming cycle with minimum edge weight as it forms the tree including every vertex where total weight of the edges in the graph minimized. It selects the smallest edge and connects without forming a cycle as the edges are chosen in ascending order of the weight to spares the graph.

Prims Algorithms: It is a greedy algorithm which finds the minimum spanning tree of undirected graph. It also contains all the vertices where total weight of all the edges minimized in the graph. This algorithm always starts with a single node and moves through several adjacent nodes, as in order to explore all of the connected edges along the path .

II. SYSTEM OVERVIEW

Prims and Kruskal’s both are greedy algorithms used to find minimum spanning tree but differ in the approach which can be used in design optimization, clustering etc. Base of both the algorithm is spanning tree. MST (minimum spanning tree) insures that all the nodes are connected with minimum no of total weight without forming a cycles . In prims algorithms it starts to build MST from any vertex and adding the smallest edge. Where as in Kruskal’s algorithms it starts to build MST by selecting a smallest edge without forming a cycle. Both the algorithms can be implemented as a software module which contains various graphs .Graph contains the vertices and the weighted edges .Prims algorithms contains the vertex based graph whereas Kruskal’s algorithms is based on the edges based and building MST by insuring that no cycle is forming. These algorithms used in real time application like

Network optimization: Designing minimum-cost communication networks. Connecting power stations with minimal wiring. Grouping data points in machine learning and data mining.

III. METHODOLOGY

This paper tells us that both the prims and Kruskal’s algorithms used to find MST (minimum spanning tree ) focusing on their efficiency and applicability across different graph types. Prim’s algorithms is implemented by using both adjacency matrix and adjacency list. Whereas Kruskal’s algorithms is implemented by edge sorting keeping in mind that cycle is not forming. In both algorithms Graph is made by using vertices and the edges. Now looking forward steps to find the minimum spanning tree by using prims and Kruskal’s algorithms. Prims Algorithms: First start with any vertex then mark it as a visited Maintaining a priority queue (or min-heap) to keep track of the edges with the smallest weight. Then we have to find the smallest edge which connects a visited vertex to an unvisited vertex with adding this edge in MST. As we have to mark all the newly connected vertices in our visited list .If the edges are not connected to unvisited vertices then we have to add that edges to priority queue now we are going to analyze given problem.

Fig a :- Prims algorithm

Steps to solve problem by using prims algorithm

1. Start from any vertex
2. In this problem we have selected v1 vertex
3. Now we are going to select next vertex which is closer to v1 vertex
4. Now we have selected next vertex as v3 because it is closer to v2
5. Next selecting v4 vertex we have to select vertex as it not making any closed loop
6. We are now moving towards the v5 vertex as any closed loop is not forming
7. Calculating total weight that is (1+3+4+2) is 10 we have find shortest path

Fig i :- Kruskal’s algorithm

Steps to solve the problem by using Kruskal’s algorithm

1. Start from any vertex as we have selected vertex 1
2. Now we have to check which vertex having smallest weight among all vertices connected to same node
3. As we move to 2 node whose vertex having weight is 2
4. Then move to next node and selecting vertex which is having smallest weight
5. Then we select node 3 whose vertex again having smallest weight which is 3
6. Again we are going back to node 2 because node 0 will make closed loop as we move next vertex
7. Now calculating total weight that is (3 +3 +7+ 2) is 14

IV. FUTURE SCOPE

Future scope of Prims and Kruskal’s algorithms both can be used in Data communication and cloud computing for Improving the energy efficiency in cloud systems by optimizing resource allocation and data flow. These algorithms can be used in the Machine Learning and Artificial intelligence like Leveraging these algorithms for scalable clustering in high-dimensional data. For Designing the cost-effective power distribution networks. We can also use Algorithms for Addressing energy storage and distribution in smart grids using MST principles as well as for Addressing NP-hard variations of the MST problem there are lot of uses of these algorithms.

V. RESULT

The following table compares two Algorithms methods, with respect to the time complexity, accuracy achieved, factors taken into the table , and advanced techniques, with an accuracy of 96%, and it considers factors like distance.

Conclusion

In conclusion, Prims and Kruskal’s algorithm offers a practical approach to enhancing the efficiency and reliability of networks. Prim\'s and Kruskal\'s algorithms methods are used to find the minimum spanning tree (MST). Both algorithms use to find the same type of problems but their approach and methods are different . Prim\'s algorithm is a greedy algorithm which starts with a single vertex and grows the MST by adding the minimum weight edge. Whereas in Kruskal’s algorithm is also a greedy algorithm but works by sorting all edges of the graph according to their weight and then adding edges one by one to the MST, ensuring no cycles are formed. Final results that both gives same answer and the prims algorithms focuses on dense graph and Kruskal’s focuses on spare graph .Both algorithms can be used in different fields like data communication and cloud computing , in machine learning. These algorithms have Scope in future like Artificial intelligence and etc

References

[1] S. C and N. Madhu, \"Network Flow Algorithms-a Comparison of Routes of a Delivery Boy\", 2023 Third International Conference on Advances in Electrical Computing Communication and Sustainable Technologies (ICAECT), pp. 1-6, 2023. [2] Bernard. Chazelle, \"A minimum spanning tree algorithm with inverse Ackermann type complexity\", Journal of the ACM (JACM), vol. 47, no. 6, pp. 1028-1047, 2000. [3] P. Ayegba, J. Ayoola, E. Asani and A. Okeyinka, \"A Comparative Study Of Minimal Spanning Tree Algorithms\", 2020 International Conference in Mathematics Computer Engineering and Computer Science (ICMCECS), pp. 1-4, 2020. [4] Reema. Thareja, \"Data structures using C\", 2014. [5] T. D. Sudhakar and K. N. Srinivas, \"Power system reconfiguration based on Prims algorithm\", 2011 1st International Conference on Electrical Energy Systems, pp. 12-20, 2011. [6] Jogamohan. Medak, \"Review and Analysis of Minimum Spanning Tree Using Prim’s Algorithm\", International Journal of Computer Science Trends and Technology, vol. 6, 2018. [7] \"17 On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem (1956)\", Ideas That Created the Future: Classic Papers of Computer Science, pp. 179-182, 2020. [8] Rohit Maurya and Rahul Sharma, \"Comparison of Prim and Kruskal’s Algorithm\", Global Journal of Computer Science and Technology, vol. 23, pp. 27-33, 2023. [9] O. T. Arogundade, B. Sobowale and A. T. Akinwale, \"Prim algorithm approach to improving local access network in rural areas\", International Journal of Computer Theory and Engineering, vol. 3, no. 3, pp. 413, 2011.

Copyright

Copyright © 2024 Akanksha Sarvade , Prof. Jayshree Tamkhede. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.