Understanding Prim’s Algorithm

Prim’s algorithm is a graph-based algorithm used to find the minimum spanning tree of a given graph. It is one of the most popular algorithms used in graph theory and is commonly used to find the shortest path between two points in a graph.

It says that for a given vertex, select a Minimum weighted edge and visit the vertex.

The algorithm works by starting with an arbitrary node in the graph and then growing a tree from this node. At each step, the algorithm will add the lowest-cost edge connecting the tree to a node outside of the tree. This process is repeated until all of the nodes in the graph have been included in the tree.

It is an efficient algorithm, as it only considers edges that connect the current tree to a node outside of the tree.

Prims algorithm uses greedy approach. This means that at each step, it makes the locally optimal choice with the hope of finding a global optimum (the minimum spanning tree) at the end.

We need to maintain two properties in order to use this algorithm:

• Vertex needs to be connected.
• It should maintain tree property (should not create cycles).

Let’s take an example and try to understand the working of Prim’s algorithm:

Graph with weighted edges

We have a graph and we need to create a spanning tree.

Spanning tree is a subset of a graph that will have n vertex and n-1 edges.

Let’s use Prims algo to create the minimum spanning tree that has all the vertex and edges with minimum weight.

First, let’s start from the root node and let 1 be the root node.

• we’ll check which edges has minimum value, 1 is connected with 6 and 2, Clearly 6 has a minimum weight of 10. so we connect with 6.

• Now, we need to check between 1 and 6 which one has the minimum connected edge. As we see, 6 has minimum connecting edge that is 5 with edge weight 25. Because 1 is connecting with 2 with edge 28 and 6 is connecting with 5 with weight 25, that is the reason we choose 5 with weight 25.

• Now we need to check for 1, 6and 5 to choose minimum edge, we can see 5 has a minimum edge with weight 22 connecting with 4.

• Now, we need to check for 1, 6, 5 and 4. 4 has a minimum edge with weight 12 connecting to 3.

• Now, we need to check for 1, 6, 5, 4 and 3. Out of all, 3 has a minimum edge with weight 16 connecting to 2.

• Now, we need to check for 1, 6, 5, 4, 3 and 2. Out of all, 2 has a minimum edge with weight 14 connecting to 7.

As you can see, we now have a minimum spanning tree with cost = 99.

The key to understanding Prim’s algorithm is to realize that at each step, the tree is always a minimum spanning tree of the vertices that are in the tree so far. This means that, when you look for the next edge to add to the tree, you only need to consider edges that connect the tree to vertices that are not yet in the tree, because adding any other edge would not result in a minimum spanning tree.

The time complexity of Prim’s algorithm is O(V²) in the worst case, where V is the number of vertices in the graph.

This is because the algorithm must search through all the edges incident to each vertex to find the minimum weight edge at each step.

In some cases, the algorithm may run faster with a time complexity of O(E log V) if a priority queue is used to store the minimum weight edges, where E is the number of edges in the graph.

Overall, Prim’s algorithm is a good choice for finding the minimum spanning tree of a graph when the edge weights are not already sorted. It is simple to implement and can run efficiently on most graphs.

Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we have covered few of the most commonly used algorithms using javascript.