Prim's algorithm Java

3 May 2025 | 4 min read

Prim's algorithm in Java is one of the most used algorithms for Minimum Spanning Tree. Prim's algorithm starts with a spanning tree having no vertices. In prim's algorithm, we maintain two sets of vertices in which first contains those vertices that are present in the MSP and the second one contains those vertices that are not present in the MSP.

At each step, it considers all edges that combine the two sets and selects the minimum weight edge from these edges. After selecting an edge, it sets the other end of the edge that contains the MST.

Prim's Algorithm

Create any collection that contains only unique elements keeps track of vertices already included in MST.
For all the vertices of the input graph, assign a key-value pair and set the value to infinite. In order to pick the first vertex, we set its key value as 0.
Select a vertex u that is not present in the setOfMST and having a minimum key value.
Add vertex u to the setOfMST.
Change the key value of all adjacent vertices of u.