Prim's Minimum Spanning Tree (MST): All You Need to Know

Introduction to Prim’s Algorithm

Prim’s algorithm is used to find the Minimum Spanning Tree for a given graph. But, what is a Minimum Spanning Tree, or MST for short? A minimum spanning tree T(V’, E’) is a subset of graph G(V, E) with the same number of vertices as of graph G (V’ = V) and edges equal to the number of vertices of graph G minus one (E’ = |V| - 1). Prim's approach identifies the subset of edges that includes every vertex in the graph, and allows the sum of the edge weights to be minimized.

Prim’s algorithm starts with a single node and works its way through several adjacent nodes, exploring all of the connected edges along the way. Edges with the minimum weights that do not cause cycles in the graph get selected for t inclusion in the MST structure. Hence, we can say that Prim’s algorithm takes a locally optimum decision in order to find the globally optimal solution. That is why it is also known as a Greedy Algorithm.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

How to Create MST Using Prim’s Algorithm

Let’s first look into the steps involved in Prim’s Algorithm to generate a minimum spanning tree:

• Step 1: Determine the arbitrary starting vertex.
• Step 2: Keep repeating steps 3 and 4 until the fringe vertices (vertices not included in MST)remain. 
• Step 3: Select an edge connecting the tree vertex and fringe vertex having the minimum weight.
• Step 4: Add the chosen edge to MST if it doesn’t form any closed cycle.
• Step 5: Exit

Using the steps mentioned above, we are supposed to generate a minimum spanning tree structure. Let’s have a look at an example to understand this process better.

Graph G(V, E) given below contains 9 vertices and 12 edges. We are supposed to create a minimum spanning tree T(V’, E’) for G(V, E) such that the number of vertices in T will be 9 and edges will be 8 (9-1).

• Primarily, to begin with the creation of MST, you will choose an arbitrary starting vertex. Let’s say node A is your starting vertex. This means it will be included first in your tree structure.

• After the inclusion of node A, you will look into the connected edges going outward from node A and you will pick the one with a minimum edge weight to include it in your T(V’, E’) structure. 

• Now, you have reached node B. From node B, there are two possible edges out of which edge BD has the least edge weight value. So, you will include it in your MST. 

Unleash a High-paying Automation Testing Job!

Automation Testing Masters ProgramExplore Program

• From node D, you only have one edge. So, you will include it in your MST. Further, you have node H, for which you have two incident edges. Out of those two edges, edge HI has the least cost, so you will include it in MST structure.

• Similarly, the inclusion of nodes G and E will happen in MST. 

• After that, nodes E and C will get included. Now, from node C, you have two incident edges. Edge CA has the tiniest edge weight. But its inclusion will create a cycle in a tree structure, which you cannot allow. Thus, we will discard edge CA as shown in the image below.

• And we will include edge CF in this minimum spanning tree structure. 

• The summation of all the edge weights in MST T(V’, E’) is equal to 30, which is the least possible edge weight for any possible spanning tree structure for this particular graph. 

Moving ahead, we will learn about the coding implementation of Prim’s Algorithms using the C programming language.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

Coding Implementation of Prim’s Algorithm

Prim's technique works on the simple principle that all vertices in a spanning tree must be connected. To build a Spanning Tree, the two distinct subsets of vertices should be joined and they must be connected in such a way that summation of all edge weights is minimum.

This implementation of Prim’s algorithm begins with the creation of graph structure. We will use an adjacency matrix or 2D matrix in C programming to represent the graph. This adjacency matrix will store weights and edges between different nodes of a graph.

Now, we will look into the step-by-step strategy to implement Prim’s algorithm.

1. Keep track of the vertices included in MST with the set.
2. Initialize all key values to infinity, and at runtime adjust the first vertex to 0 for selecting it as the tree's initial vertex.
3. While the Tree Set does not contain all of the vertices:

• Choose a vertex x with the smallest edge weight.
• Include x in the set.
• Update the key value of all adjacent vertices of x.

The graph for which we are going to generate a spanning tree is represented in the image below:

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

The C program to implement Prim’s algorithm using above mentioned strategy is as follows:

Learn 15+ In-Demand Tools and Skills!

Automation Testing Masters ProgramExplore Program

Output:

You can verify the output of this code by generating the least possible spanning tree for the graph shown above.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Prepare Yourself to Answer All Questions!

Automation Testing Masters ProgramExplore Program

Conclusion

In this tutorial, we discussed  Prim’s Algorithm in a data structure and how it is used to build the minimal spanning tree for a given graph topology. We also learned how to create MST for a given graph and to use the C programming language to implement it.

Simplilearn's Software Development Courses offers ideal courses for those looking for more in-depth training that is beyond data structures and covers the basics of interactive application development. The courses in the above catalog will help you master the craft of software development while also preparing you for your job hunt. Explore now and get started!

Meanwhile, if you have any questions about this tutorial on Prim’s Algorithm, please leave them in the comments section at the bottom of this page; we will respond to them soon!