What is prims algorithm with example

In this tutorial, you will learn how Prim's Algorithm works. Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which.

It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum. The pseudocode for prim's algorithm shows how we create two sets of vertices U and V-U. U contains the list of vertices that have been visited and V-U the list of vertices that haven't. One by one, we move vertices from set V-U to set U by connecting the least weight edge.

Although adjacency matrix representation of graphs is used, this algorithm can also be implemented using Adjacency List to improve its efficiency. Kruskal's algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the MST of a graph.

Instead of starting from a vertex, Kruskal's algorithm sorts all the edges from low weight to high and keeps adding the lowest edges, ignoring those edges that create a cycle. Course Index Explore Programiz. Start Learning DSA. Popular Tutorials Quicksort Algorithm. In case of parallel edges, keep the one which has the least cost associated and remove all others. In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily chosen, so any node can be the root node.

One may wonder why any video can be a root node. So the answer is, in the spanning tree all the nodes of a graph are included and because it is connected then there must be at least one edge, which will join it to the rest of the tree.

After choosing the root node S , we see that S,A and S,C are two edges with weight 7 and 8, respectively. We choose the edge S,A as it is lesser than the other. Now, the tree SA is treated as one node and we check for all edges going out from it. We select the one which has the lowest cost and include it in the tree.

If there are multiple choices then choose anyone. Already have an Account? Sign In Name E-mail Password. Sign Up Lost your password? What is a Minimum Spanning Tree?

Prim's Algorithm for Minimum Spanning Tree Prim's algorithm basically follows the greedy algorithm approach to find the optimal solution. Get Help Now. About The Author. Shivali Bhadaniya I'm Shivali Bhadaniya, a computer engineer student and technical content writer, very enthusiastic to learn and explore new technologies and looking towards great opportunities. It is amazing for me to share my knowledge through my content to help curious minds.