Prim’s Algorithm Minimum Spanning Tree in Java, easy in 5 minutes

Today, I introduce you to Prim’s Algorithm Minimum Spanning Tree in Java and how to use it finding the minimum spanning tree. Sometimes, Prim’s Algorithm is called Minimum Spanning Tree (MST) algorithm, it takes a graph as input and produces a MST tree.

Prim’s Algorithm Minimum Spanning Tree in Java

What’s Prim’s Algorithm?

Prim’s algorithm is a greedy algorithm and it is used to find a minimum spanning tree for a weighted undirected graph.

Minimum Spanning Tree

A MST tree has some properties:

  • It includes all vertices of graph.
  • It has a minimum possible number of edges of graph.

 

Minimum spanning tree, Prim's Algorithm Minimum Spanning Tree in Java

Please have a look at this picture. You will see a MST tree that is a part of graph.

How Prim’s algorithm works

In this post, we will use a graph in the above picture as input for this algorithm and this grap is represented in the adjacent matrix. In general, we start from any one vertex then add adjacent vertex with the edge that is the lowest weight until we reach to all vertices of the graph. Implementation of the algorithm follows the steps:

  1. Create MST like an array to store all vertices of the graph later. Then initialize the first element of this array is a random vertex of the adjacent matrix.
  2. Find all the edges of vertices in MST tree with new vertices in graph. Find the edge is with the minimum weight then add a new vertex in MST tree.
  3. Keep repeating step 2 until we reach all vertices of graph. The we get a MST tree.
Implementation of Prim’s algorithm in Java

Here, we reuse the source code of the previous post to implement Prim’s¬†Algorithm Minimum Spanning Tree in Java. we just add some methods for algorithm implementation.

Here is output of the above program

Time Complexity:

Time Complexity of the above program is O(V2). Because we are using a graph in adjacency matrix

as input.

That’s all about Prim’s Algorithm Minimum Spanning Tree in Java.

References

Graph documentation
Graph Data Structure in Java

Please share it if you found this useful
Hide Buttons