.

# Prim's algorithm Assignment Help

**Prim's algorithm** is a greedy algorithm that finds a minimum spanning tree for any connected weighted undirected graph. This means it finds a subset of the edges that forms a tree which includes each and every vertex, in which the complete weight of all the edges in the tree is minimized. It's also known as the **DJP algorithm**, the **Jarník algorithm**, or even the **Prim-Jarník algorithm**.

## Pseudocode for the Prim Algorithm

- INPUT : n, c[ e(ij) ], i, j belonging to 1,...,n.
- OUTPUT : p(j) j = 2,...,n (pointer of peaks j father in the T tree).

### Prim Algorithm STEPS

1. : ( initializations ). O = {1} ( V(1) root of the T tree ). P = 2,...,n For each j belonging to P : e(j): = c[ e(j1) ] , p(j) = 1

( All peaks connected to the root. Through description from the cost function: e(j) = infinite if V(j) doesn't connect to V(1).).

2. Select a k for which e(k) e(j) for each j belong to P. In case of tight select the smaller one. Exchange the O set with the set produced by the union of the O set and {k}. Exchange the P set with the set produced by the difference of the P set and {k{. ( P- P- k ) If P = 0 then stop.

3. For every j belong to P compare e(j) with c[ e(kj) ]. If e(j) c[ e(kj) ] exchange e(j) - c( e(kj) ). Return to Step 1.

#### Prim's algorithm Example

#### CPS 542 Prim’s algorithm Assignment 5

.