Prims Algorithm
Before we dive into prims algorithm. Lets discuss what a spanning tree is.
Spanning Tree
As we all know, a graph without edges pointing in one direction is called an undirected graph, and the graph always has a path from one vertex to another. A spanning tree is a subgraph of an undirected connected graph that contains all the vertices of the graph with as few edges as possible. Remember that the subgraph should contain every node of the original graph. If a node is omitted, it is not a spanning tree, nor does a spanning tree contain loops. If the graph has n nodes, then the total number of spanning trees constructed from the complete graph is n^(n-2).
Minimum Spanning Tree
Edges in a spanning tree may or may not have associated weights. Therefore, a spanning tree whose sum of edges is as small as possible is called a minimum spanning tree. A graph can have multiple spanning trees, but it can only have a unique minimum spanning tree. There are two different methods for finding the minimum spanning tree from the whole graph, namely Kruskal’s algorithm and Prim’s algorithm.
Prims Algorithm
Prim’s algorithm is a minimum spanning tree algorithm that helps to find the edges of a graph to form a tree, including the nodes with the smallest sum of all weights to form a minimum spanning tree. Prim’s algorithm starts with a single source node and then examines all of the source node’s neighbors and all connected edges. When we examine the graph, we will choose the edges with the smallest weights and those that do not cause cycles in the graph.
Prim’s algorithm follows the greedy algorithm approach to find the optimal solution. To find the minimum spanning tree using Prim’s algorithm, we choose a source node and add the edge with the lowest weight.
The algorithm is as follows:
- Initialize the algorithm by selecting a source node.
- Find the minimum weight edge connecting to the source node and another node and add it to the tree.
3. Repeat this process until we find the minimum spanning tree.
Time complexity
The running time of prim’s algorithm is O(VlogV + ElogV), which is equal to O(ElogV) because each insertion of a node into the solution takes logarithmic time. where E is the number of edges and V is the number of vertices/nodes. However, we can increase the runtime complexity to O(E + logV) of prim’s algorithm by using a Fibonacci heap.
Applications of Prims Algorithm
- Prim algorithm for network design
- It is used to connect all the city’s network bikes and rails
- Use Prim’s algorithm when laying wires
- Prim algorithm for the erection of irrigation canals and microwave towers
- It is used for cluster analysis
Pseudocode
This Pseudocode is taken from https://www.softwaretestinghelp.com/minimum-spanning-tree-tutorial/
