Prim’s Algorithm

Prim’s algorithm searches minimum spanning tree in a weighted undirected graph. In other words, it finds a sub-set of edges that forms a tree, where all vertices of a given graph are included and total weight of all edges is minimized.

Let’s consider the following example. You are an engineer and you’re going to build electrical grid to provide electricity to all houses bellow. The weight represents distance between two houses.

pa_main_1

Of course, the houses can be connected in a random way and the problem will be solved.

pa_main_2

But, you are a smart engineer and you can do better. Because, you think on how to minimize the cost of wire. For this, you can use Prim’s algorithm which will produce MST that will show you how the houses should be connected.

pa_main_3

As you can see the difference between 63 and 41 is significant.

Algorithm
  1. Given a weighted undirected graph.pa_example_01
  2. Choose an arbitrary vertex.pa_example_002
  3. Choose the shortest edge from this vertex.pa_example_003
  4. Choose the shortest edge from vertices 2 and 3.pa_example_4
  5. Choose the shortest edge from vertices 2, 3 and 4.pa_example_5
  6. Choose the shortest edge from vertices 2, 3, 4 and 5.pa_example_6
  7. Choose the shortest edge from vertices 1, 2, 3, 4 and 5.pa_example_7
  8. That is all, our minimum spanning tree is found.
Prim’s algorithm vs. Kruskal’s algorithm

Both Prim’s algorithm and Kruskal’s algorithm are very common greedy algorithms that can be used to find minimum spanning tree. But, they solve the problem in absolutely different ways. The main difference is that Kruskal’s algorithm looks globally on all edges and selects minimum edge that does not form a cycle. The Prim’s algorithm selects an arbitrary vertex and then grows MST by adding another vertices that is not yet in MST and has minimum weight. In other words, Prim’s starts with a node, whereas Kruskal’s starts with an edge. Prim’s algorithm spans from one node to another while Kruskal’s algorithm selects the edges in a way that the position of the edge is not depends on the previous step.

In terms of time complexity, the Kruskal’s algorithm has Ο(E log V) time complexity, the Prim’s algorithm that is based on binary heap or adjacency list has Ο (E log V) complexity and if it’s based on Fibonacci heap it has Ο (E + V log V) complexity. Therefore, Prim’s algorithm is faster on dense graphs.

Implementation

Here goes my Java version of Prim’s algorithm on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/PrimsAlgorithm.java.

Leave a Reply