# What Is Prims Algorithm in Data Structure?

//

Larry Thompson

Prims Algorithm is a popular algorithm used in data structures to find the minimum spanning tree of a weighted undirected graph. It was developed by Jarník and later independently discovered by Prim in 1957. This algorithm ensures that all vertices of the graph are connected with minimum total edge weight.

## Understanding Prims Algorithm

Prims Algorithm starts with an arbitrary vertex and grows the minimum spanning tree by adding edges to connect the nearest vertex that is not yet connected. The algorithm maintains two sets: one set contains the vertices already included in the minimum spanning tree, and the other set contains the vertices not yet included.

### Step-by-Step Procedure:

• Step 1: Start with an empty set for the minimum spanning tree.
• Step 2: Select a starting vertex arbitrarily and add it to the minimum spanning tree set.
• Step 3: While there are vertices not yet included, do:
• A: Find the minimum weight edge that connects a vertex from the minimum spanning tree set to a vertex outside of it.
• B: Add this selected edge to the minimum spanning tree set.

### Pseudocode for Prims Algorithm:

The following is a simplified pseudocode representation of Prims Algorithm:

```function Prim(graph):
initialize empty set MST
select any starting vertex s from graph
initialize an empty priority queue Q

while Q is not empty:
u = extractMin(Q)

for each neighbor v of u:
if v is not in MST:
if edge weight(u, v) < key[v]:
update key[v] to edge weight(u, v)
update parent[v] to u
decreaseKey(Q, v)

return MST
```