Prim's algorithm to find a minimum spanning tree in Java With Examples

A minimum spanning tree aka minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph. This subset connects all the vertices together, without any cycles and with the minimum possible total edge weight.

There can be more than one minimum spanning tree for a graph. The overall cost, however, will be the same for different MSTs of the same tree.

Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that finds the MST for a weighted undirected graph.

The algorithm proceeds by building MST one vertex at a time, from an arbitrary starting vertex. At each step, it makes the most cost-effective choice. That is, it optimizes locally to achieve a global optimum.

The way Prim’s algorithm works is as follows :

  1. Initialize the minimum spanning tree with a random vertex (initial vertex).
  2. Find all the edges that connect the tree to new vertices, find the minimum, and add it to the tree (greedy choice).
  3. Keep repeating step 2 until we get a minimum spanning tree (until all vertices are reached).

We can look at an example to understand how Prim’s algorithm works.

Let the weighted undirected graph be as follows :

We choose 0 as the initial vertex.

We choose 0 as the initial vertex.

We choose 0 as the initial vertex.

As the next step, we choose the minimum from all the nodes connected with the MST.

At each subsequent stage, we find the minimum-cost edge that connects the tree to a new vertex.

We choose 0 as the initial vertex.

Using 4 edges we’ve connected all the 5 nodes. The cost of the minimum spanning tree is the sum of all the edge weights.

In this example, it is :

Prim’s Algorithm Java Code

The java implementation is as follows.

Code for Graph class :

Main class :

Output

We choose 0 as the initial vertex.

Output

We can verify the output using the example above.

Conclusion

This tutorial was on Prim’s algorithm to find out the minimum spanning tree for undirected weighted graphs. Hope you enjoyed learning about Prim’s algorithm.

By admin

Leave a Reply