Comparative applications of Prim’s and Kruskal’s algorithm in real-life scenarios

Welcome! Let’s start with some informal context. Let me ask you something:

✅ Do you use Google Search?
✅ Do you use Google Maps?
✅ Do you use social media sites?

If “Yes” to any of these questions, then you’ve definitely used graphs and you didn’t even know it! Surprised? I was, too! Through this blog, we will go through two essential, yet fun algorithms and compare them in real-world scenarios.

These data structures really caught my attention due to their amazing capabilities and diverse real-world applications. Let’s begin!?

Let’s say our task is to set up lines in such a way that all the houses are connected and the cost of setting up the whole connection is minimum. Now how do we find that out? We can use Prim’s Algorithm or Kruskal’s Algorithm.

Both Prims And Kruskal Algorithms are used to find the minimum spanning trees. Now the applications of the Kruskal and Prims Algorithm are basically the applications of MST. Both approaches are known as ‘greedy’ algorithms. So now What is a ‘greedy’ algorithm?

A greedy algorithm is a method that follows the problem-solving technique of making the locally optimal choice at each stage with the hope of finding a global optimum.

Both the algorithms are just two similar hands of a minimum spanning tree. What left me wondering was when one should use Prim’s algorithm and when Kruskal’s to find the minimum spanning tree? They both have easy logics, the same worst cases, and the only difference is the implementation which might involve a bit different data structure. So what is the deciding factor?

The basic difference is in which edge you choose to add next to the spanning tree in each step.

In Prim’s, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighboring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.

In Kruskal’s, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.

Now I recommend you all to go in the technicals of both the algorithms through other blogs and learn the difference in the implementations of both.

The key to choose between Prim’s and Kruskal’s algorithm for an application is to study the structure of the application itself.

Just try and convert your application in a graphical representation with vertices and edges:

For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) time, if you use a Fibonacci heap. Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph (many more edges than vertices). Kruskal performs better in typical situations (sparse graphs) and is easier to implement because it uses disjoint sets and simpler data structures. Whereas, Prim’s algorithm uses adjacency matrix, binary heap or Fibonacci heap. Depending upon the stated points, we can have a comparative idea of choosing an algorithm for a particular application.

Applications where Kruskal’s algorithm is generally used:

1. Landing cables

2. TV Network

3. Tour Operations

4. LAN Networks

5. A network of pipes for drinking water or natural gas.

6. An electric grid

7. Single-link Cluster

Applications where Prim’s algorithm is generally used:

1. All the applications stated in the Kruskal’s algorithm’s applications can be resolved using Prim’s algorithm (use in case of a dense graph).

2. Network for roads and Rail tracks connecting all the cities.

3. Irrigation channels and placing microwave towers

4. Designing a fiber-optic grid or ICs.

5. Travelling Salesman Problem.

6. Cluster analysis.

7. Pathfinding algorithms used in AI(Artificial Intelligence).

8. Game Development

9. Cognitive Science

Continue learning about these amazing data structures! It will be totally worth it for your future as a developer. I’m learning about data structures right now, and I find them completely fascinating.

The important thing is to not stop questioning. Curiosity has its own reason for existing.

-Albert Einstein

Thank you!

I really hope that you liked my blog.