Exploring Prim’s Algorithm

Most of the algorithms of interest operate on data. There are some arrangements of organizing data that play a critical role in the design and analysis of algorithms. In simple words, we can say that data structures are simply ways of organizing data.

Data structures are of two types, either linear or nonlinear. Linked lists and arrays are examples of linear data structures. Trees and graphs are some types of nonlinear data structures.

Algorithms are methods of execution of the problems. In this blog, we will explore the Prims algorithm which is used to find the minimum spanning tree from a graph.

Before we start with Prims Algorithm let us understand a few terms:

1. Graphs: A graph is a data structure, nonlinear in nature consisting of nodes and edges. The nodes here are sometimes also known as vertices and the edges are lines or arcs that connect any two nodes in the graph.

2. Trees: Trees are also nonlinear data structures with a structure like a graph. The main difference in a tree is that Trees have exactly one path between two vertices. There cannot be more than one route between 2 vertices.

3. Minimum Spanning Tree: A Minimum Spanning Tree is a subset of edges in a graph that connects every vertex and minimises the total of the edges. The sum of the weights given to the edges of the spanning tree is the weight of the spanning tree.

Now let’s move on to the main topic of discussion, Prim’s Algorithm. It is a greedy algorithm used to find the minimum spanning tree. Prim’s algorithm identifies the subset of edges that includes every vertex in the graph and allows the sum of the edge weights to be minimized. We start by taking any node at random and then move ahead by connecting the other nodes, making sure that we do not make a graph, i.e., there is only one way from one node to another.

The algorithm:

Step 1: Select a starting node at random.

Step 2: Repeat Steps 3 and 4 until there are fringe nodes.

Step 3: Select an edge ‘e’ connecting the tree node and fringe node that has a minimum weight

Step 4: Add the selected node and the edge to the minimum spanning tree T

[END OF LOOP]

Step 5: EXIT

Now, Let’s look at an example:

Step 1 — First, we must choose a node randomly from the above graph. Let’s choose B.

Step 2 — Now we must select and combine the shortest edge from vertex B. There are two edges from vertex B: B to C, which has a weight of 10, and B to D, which has a weight of 4. The edge BD has the lightest weight of all the edges. As a result, add it to the MST.

Step 3 — Among all the edges, choose the one with the least amount of weight. The edges DE and CD are examples of such edges in this context. Add them to MST and investigate the areas next to C, namely E and A. As a result, choose the edge DE and add it to the MST.

Step 4 — Now, as we can see the weight on CD is the least, select the edge CD, and add it to the MST.

Step 5 — Now, we can see that node A is the only node left and it is only connected to C, so we choose the edge CA and add it to the MST.

Now we can calculate the cost of the MST, which is given below-

Cost of MST = 4 + 2 + 1 + 3 = 10 units.

I hope this blog made your understanding of Prim’s Algorithm a little bit better.