A Prim’s algorithm comes under a greedy algorithm and is used to discover the minimum spanning tree from a graph.
Beginning with a single node, Prim’s algorithm analyses each subsequent node along with all of its associated edges.
Table of Contents
- How Does Prim’s Algorithm Work?
- Example of Prim’s Algorithm
- Algorithm
- Prim’s Algorithm Complexity
- Prim’s Algorithm Application
How Does Prim’s Algorithm Work?
It belongs to a category of algorithms known as greedy algorithms, which discover the local optimum with the intention of discovering a global optimum.
Beginning with one vertex, we continue to add edges with the lowest weight until we attain our objective.
Executing Prim’s algorithm involves the following steps:
- Set up the minimum spanning tree using a randomly chosen vertex.
- Find the minimum of all the edges connecting the tree to further vertices, then add it to the tree.
- Repeat step 2 as necessary to obtain a minimum spanning tree.
Example of Prim’s Algorithm
We will begin with a graph which is weighted.
Then, select a vertex.
From this vertex, pick the shortest edge and add it.
Now, choose the closest vertex that is not yet included in the solution.
Select the nearest edge. If more than one option is available, pick one at random.
Continue this process until a spanning tree is formed.
Algorithm
Stage 1: Choose a starting vertex
Stage 2: Repetition of Steps 3 and 4 until the fringe vertex is present.
Stage 3: Choose an edge with a minimum weight that connects the tree vertex and the fringe vertex.
Stage 4: Include the chosen vertex and edge in the least spanning tree T.
[FINISH OF LOOP]Stage 5: EXIT
Prim’s Algorithm Complexity
The time complexity of Prim’s algorithm is O(E log V).
Prim’s Algorithm Application
- Installing electrical wiring lines
- In designing the network
- To build protocols in network cycles
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
