Cybercrimes and solutions

Comparative applications of Prim's vs Kruskal's algorithm in real life scenarios.

Have you ever wondered how do Google maps find the best route to your destination? Well, it doesn’t practically read the maps, but uses some algorithms to determine the shortest path to your destination. Although it involves other complications too, such as analyzing the traffic or finding alternative routes if the roads are temporarily blocked etc., the task is solved using the concepts of graph theory. The network of roads is considered as a directed graph with intersection of roads and landmarks to be vertices and the roads to be edges.

In this article, we would be comparing some real life applications of Kruskal’s and prim’s algorithms which are basically used to route the shortest length of the path in a network.Speaking in graph theory terminologies, these algorithms are used to find the minimum spanning trees (MST). Spanning tree is the sum of weights on all edges of the tree. An MST is the one which costs the least among all spanning trees.

As we see, both these algorithms have easy logic, same worst cases, and only difference is implementation which might involve a bit different data structures. So what is the deciding factor?

Let us understand the time complexities of both these algorithms.Prim’s algorithm has a time complexity of O(V^2) and Kruskal’s is O(log V). Hence we can see that prim’s algorithm works faster in dense graphs having more no. of vertices while Kruskal’s algorithm works faster in sparse graphs.From looking at prim and kruskal, you can see that the general principle is similar. You pick the minimum weight edge that doesn’t create a cycle. The order that you pick these edges doesn’t matter much. After examining different minimum spanning trees it can be stated that all of them lead to the same results but with different approaches.

Where do we use these algorithms and how do they work?

• ·       Designing a network
  

Talking of a common example in network building, let’s consider a cable network which is to be laid in a specific area. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.The same could be applied to other networks such as, LAN, electric wiring, telephone line or sewage pipelines.Here considering this network to be a dense graph having large concentration of houses and buildings (vertices) in an area, prim would work better.

 If we wish to connect different neighboring cities through railway lines or highways, these algorithms would be beneficial to find the efficient routes having minimum spanning.

As we see, when connections are to be laid between a numerable cities, we can consider this to be a sparse graph and hence Kruskal’s algo would be fast enough to plot the MST.

• Constructing a maze

Another interesting application of prim’s algorithm is the generation of mazes. A maze can be generated by starting with a predetermined arrangement of cells with walls between them. This predetermined arrangement can be considered as a connected graph with the edges representing possible walls and the nodes representing cells. The purpose of the maze generation algorithm can then be considered to be making a sub-graph in which it is challenging to find a route between two particular nodes.

While these are some of real life applications of kruskal’s and prim’s algorithms to find minimum spanning trees, other areas of application include-Topology, cartography, geometry, clustering, routing algorithms, study of molecular bonds in chemistry, network designing etc.

So looking at the applications we can conclude that Kruskal’s algorithm is clearly more useful if applied to the real world, while prim’s runtime grows faster with the order of the graph to be of use in serial processing environment. 

 Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.