# Prim's Algorithm

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.

## 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 CriteriaGATE 2023GATE Admit CardGATE Syllabus for CSE (Computer Science Engineering)GATE CSE NotesGATE CSE Question Paper, and more.

Also Explore,