## DEV Community

Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

# Minimum Spanning Tree (Prims Algorithm)

Given a weighted, undirected and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.
Example 1:

The Spanning Tree resulting in a weight
of 4 is shown above.

``````class Solution
{
//Function to find sum of weights of edges of the Minimum Spanning Tree.
// its similar to dijkstra's single source shortest path algorithm
static int spanningTree(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj)
{
boolean mstSet[] = new boolean[adj.size()];// this is nothing but visited nodes , that have become part of already chosen
Arrays.fill(key,1000000000);// writing 1e9 means the nodes are yet to be discovered
key[0] =0; // node 0
PriorityQueue<Pair> q = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
//let the starting node be 0
q.add(new Pair(key[0],0)); //distance of 0 from 0 is 0
while(!q.isEmpty()){

Pair p = q.remove();
mstSet[p.getKey()] = true;
//System.out.println("node is "+p.getKey() + " d from node 0 is "+ p.getValue());
// below if statement will mean that this adjacent node of node p.getKey()  has not been taken
if(mstSet[l.get(0)]== false && key[l.get(0)] > l.get(1)){
key[l.get(0)] = l.get(1);