The Finest Guide to Understand and Implement Prim’s Algorithm from Scratch

Did you know Prim’s Algorithm is used to manage Internet Radio Broadcasting to transfer information to the listeners efficiently? An efficient transfer is vital for Internet radio so that all the listeners that are tuned in receive the whole data they need to reconstruct the songs they’re listening to. So, in this article, we are going to learn this algorithm in detail. The topics covered in this article are:

  1. Introduction to Prim’s Algorithm
  2. How to Create MST Using Prim’s Algorithm
  3. Coding Implementation of Prim’s Algorithm

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.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

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).

Graph_G_for_Constructing_MST.

  • 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.

Prims_step1.

  • 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. 

Adding_1st_Edge_in_MST.

  • 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. 

Adding_2nd_Edge_in_MST-Prims_Algorithm.

  • 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.

Edge_inclusion_MST-Prims_Algorithm.

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

Inclusion_node_E-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.

Edge_descarding_in_Prims_Algorithm

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

Final_MST.

  • 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.

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:

Graph_for_Coding_Implementation.

Add Another Star to Your Performance Evaluation

Learn from industry experts for FREEStart Learning
Add Another Star to Your Performance Evaluation

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

//Library to access INT_MAX variable

#include <limits.h>

//Library to create set

#include <stdbool.h>

#include <stdio.h>

#define Vertices 5

//A utility function for finding the vertex with the lowest key value from a set of vertices that isn't included in MST.

int Least_Key(int key[], bool Min_Span_Tree[])

{

    int least = INT_MAX, min_index;

    for (int v = 0; v < Vertices; v++)

        if (Min_Span_Tree[v] == false && key[v] < least)

            least = key[v], min_index = v;  

    return min_index;

}

//Function to print created MST

int print_Prims_MST(int parent[], int graph[Vertices][Vertices])

{

    printf("Edge \tWeight\n");

    for (int i = 1; i < Vertices; i++)

        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);

}

//Function to generate MST

void prims_MST(int graph[Vertices][Vertices])

{

    int parent[Vertices];

    int key[Vertices];

    bool Min_Span_Tree[Vertices];

    for (int i = 0; i < Vertices; i++)

        key[i] = INT_MAX, Min_Span_Tree[i] = false;

    key[0] = 0;

    parent[0] = -1; 

    for (int count = 0; count < Vertices - 1; count++) {

        int u = Least_Key(key, Min_Span_Tree);

        Min_Span_Tree[u] = true;

        for (int v = 0; v < Vertices; v++)

            if (graph[u][v] && Min_Span_Tree[v] == false && graph[u][v] < key[v])

                parent[v] = u, key[v] = graph[u][v];

    }

    printf("Created Spanning Tree for Given Graph is: \n");

    printf("\n");

    print_Prims_MST(parent, graph);

}

int main()

{

    int graph[Vertices][Vertices] = { { 0, 3, 0, 6, 0 },

                        { 3, 0, 4, 8, 5 },

                        { 0, 4, 0, 0, 7 },

                        { 6, 8, 0, 0, 11 },

                        { 0, 5, 7, 11, 0 } };

    prims_MST(graph);

    return 0;

}

Output:

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

Prim's_Algorithm_Output

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

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!

About the Author

Sayeda Haifa PerveezSayeda Haifa Perveez

Haifa Perveez is passionate about learning new technologies and working on them. She is an engineer who loves to travel, read and write. She's always curious about things and very determined to track the latest technologies and the trends that they are creating for the future.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.