Group 13 SY-IT-A Data Structure Blog Writing Home Assignment. Submitted to Mrs. Shital Dongre Mam.

 

VISHWAKARMA INSTITUTE OF TECHNOLOGY

UPPER INDIRA NAGAR, BIBWEWADI, PUNE-37

HOME ASSIGNMENT SUBMISSION: BLOG WRITING

TOPIC: COMPARATIVE APPLICATIONS OF PRIM’S VS KRUSKAL’S ALGORITHMS IN REAL LIFE SCENARIO                                                                       DATE: 10-12-2020

                                                                                                                           THURSDAY

GUIDE: PRO. MRS. SHITAL DONGRE

MEMBERS: ROLL NO 14: YOGESH CHAUDHARI

ROLL NO 16: PRASANNA DANI

ROLL NO 17: PRUTHVIRAJ DESHMUKH

ROLL NO 25: CHETAN JAIN

ROLL NO 72: SHREYAS TOSHNIWAL

 

COMPARATIVE APPLICATION OF PRIM’S VS KRUSKAL’S ALGORITHM IN REAL LIFE SCENARIO

So, you might be using the navigation map. You might be using the google search. If yes, so it means you are using our graph data structures. Surprised? Don’t wry! Continue reading our blog and you will get the exact idea behind it with proper technical knowledge.

So, Let’s begin 😊

Before beginning with our topic, let us focus on Prim’s and Kruskal’s algorithm. Even before that, we need to focus on MST, which is Minimum Spanning Tree. So, a minimum spanning tree (MST) is nothing but a tree of a special kind, that decreases the lengths of edges of the tree to their minimum limits. Minimizing the edges will decrease the total length of such a spanning tree, the so-called minimum spanning tree.

For example, if a technician of cable network office wants to lay cables for 5 houses in my area, so minimum spanning tree among those houses will save his cable from been used more than the need.

So, moving towards the properties, we can find that if there are n vertices in the graph(tree), then the number of edges in that MST will be n-1.

One more property to mention is if all the edges of the given graph weighs the same, then every spanning tree been formed can be an MST.

But it's not like every graph will have a unique minimum spanning tree. If two or more edges are weighing the same, so there might be a possibility that we can get multiple minima spanning trees, but a multiset of weight in MST remains unique.

 

For example:

MST’s:

1}

2}

So now, we need to follow some properties which makes a spanning-tree the Minimum Spanning Tree.

First is cycle property: let there is a cycle formed in a graph, named C (say), the edge of that cycle which weighs maximum among all the edges of the same cycle, let say edge e can not be the part of Minimum Spanning Tree. It means, no cycle is allowed in MST and to avoid cycle, the edge with maximum weight is that cycle is removed.

Cut property: cut set includes the set of edges in which the one terminal or endpoint of the set belongs to one graph and the other endpoint to another graph. So, during the construction of a minimum spanning tree, assuming all the edges cost in MST is distinct, the original graph is nothing but the weighted and connected graph.

 

Now moving towards Prim’s Algorithm,

So, in computer science, Prim’s Algorithm is Minimum Spanning Algorithm of Greedy type. This algorithm accepts the input in the form of a graph and gives the subsets of that graph’s edges, which further gives a tree which includes every of their vertex in it and sum weights in all the trees that could be formed using that graph is minimum here.

Starting with one vertex, we keep adding the edges with the lowest weight till we get the MST.

Let’s look towards the procedure:

Step1: starting with a weighted graph.

Step2: Choose any one vertex.

 

Step3: choose the shortest vertex attached to it in the graph and add it here.

 

Step4: choose the nearest vertex which is still not in our solution tree.

 

Step5: repeat the same. If there exists multiple, choose any of them at random.

 

Step6: continue the same till we get the MST of our weighted graph.

So now, let’s have a look towards Kruskal’s algorithm, so then after we can move towards our topic with a better idea.

Again, the same. In computer science, Kruskal’s Algorithm is Minimum Spanning Algorithm of Greedy type. This algorithm also accepts the input in the form of a graph and gives the subsets of that graph’s edges, which further gives a tree which includes every of their vertex in it and sum of weights in all the trees that could be formed using that graph is minimum here too…but, steps of implementation in Kruskal’s algorithm is quite different, which is as follows.  

Step1: start with a weighted graph.

Step2: choose the edge of minimum weight in a graph. If multiple, choose any one.

 

 

 

Step3: choose the nearest edge, which is the shortest and add it to the tree.

Step4: now choose the nearest shortest edge that doesn’t make a cycle in the tree.

 

Step5: Repeating step4.

 

 

Step6: continue doing the same till we get our required MST.

Applications where Kruskal's algorithm is generally used:

• Landing cables: So, in cable works, we need the shortest length of total cable to be used to decrease the cost. This need is fulfilled by Kruskal’s algorithm.

 

• TV Network: Even signals do find the shortest path to reach the satellite or to the destination, so Kruskal’s algorithm fits here too.

 

• Tour Operations: When we plan a tour for 3 cities, we do find the shortest path to reach all 3 cities efficiently and to save energy and fuel. On the grand scale, we make an MST between our destination and our departure place, using Kruskal’s algorithm.

 

 

• LAN Networks: even LAN cables can be saved from being used extra without reason by creating MST using Kruskal’s Algorithm.

 

• A network of pipes for drinking water or natural gas: Manufacture cost of pipes and energy can be saved if we plot a shortest path using MST and Kruskal’s algorithm to create a network of pipes.

 

 

• An electric grid: Power Grid also works on Kruskal’s Algorithm to make their service cables reach their destinations in a cheaper and less stressed way.

 

Applications where Prim's algorithm is generally used:

·        Firstly, we need to clarify that all the applications of Kruskal’s Algorithm can also be resolved using Prim’s Algorithm. We can use Prim’s Algorithm in case of a dense graph.

·        Road and Rail Networks: Roads and Rail tracks that connect all the cities are usually the shortest and effective path between the two cities, that can be achieved by Prim’s Algorithm.

·        Irrigation channels: Irrigation channels in the farm also requires the shortest path and effective too, that a single channel can provide service to maximum possible farms in that locality. This can be achieved by the Prim’s Algorithm.

·        Microwave towers: Microwave towers provide the wave network in remote area and to make maximum area grasped under these towers, they also need to be installed in MST, so Prim’s algorithm is used.

·        Game Development: In many games, we find shortest path applications, like in snake game, etc. Even in adventure and shooting games, the shortest path is a must. So, Prim’s Algorithm can be used to achieve it.

·        Artificial Intelligence: Pathfinder Algorithm in the Artificial Intelligence is also based on the shortest pathfinder of Prim’s Algorithm.

Observation: So, after a keen observation of the applications, you can see that Kruskal’s Algorithm is used more than Prim’s. So, we can predict that usage of Kruskal’s algorithm is quite effective than Prim’s Algorithm, and yes, our prediction is correct too.

So, let's focus on the disadvantages of Prim’s Algorithm:

1) All possible spanning trees are to be found if more than one edges are having the same edge weight to get the final MST.

2) List of edges are to be searched from the initial point when the new edge is to be added.

Now, when we know the disadvantages of Prim’s Algorithm, we can differentiate their usage according to their abilities on the following basis.

·        So now, we can use Prim’s Algorithm when we have a graph with a lot of edges.

·        So, it is clear that Prim’s Algorithm is way faster than the Kruskal’s Algorithm when we really get a denser graph, with many more edges than the vertices.

·        Talking about Kruskal’s Algorithm, it can be easily and effectively used in sparse graphs, as it uses the simpler data structures.

 

REFERENCES:

[1] Charles M. and Hartman I. Graph theory, combinatorics and algorithms, interdisciplinary applications pg. 35, 2005 Springer, Columbia.

[2] Carmen T.H, Leiserson C.E., Rivets R.L., and Stein C., Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, 2001, pg. 567-574.