Prim Algorithm for minimum spanning trees | Prim’s Algorithm Example in Data Structure

• Prim’s algorithm to find minimum cost spanning tree.
• A Spanning Tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges.

• A spanning tree does not have cycles and it cannot be disconnected.
• In a weighted graph, a Minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph.
• Prim’s algorithm shares a similarity with the shortest path first algorithms.
• Prim’s algorithm is also a Greedy algorithm.

prim’s algorithm

Step 1 — Remove all loops and parallel edges
Step 2 — Choose any arbitrary node as root node
Step 3 — Check outgoing edges and select the one with less cost.

Step-1 firstly we remove all parallel edges and self loop, in above example there are one self loop and one parallel edge ( as mentioned using dotted line below)

Applications of Minimum Spanning Tree:-

read complete article click here

check video tutorial notes for prim’s algorithm

https://youtu.be/fgLfsA8fr-E

Originally published at https://pywix.blogspot.com.