DEV Community

Prashant Mishra
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:
image
Image description

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) 
    {
        // Add your code here
        boolean mstSet[] = new boolean[adj.size()];// this is nothing but visited nodes , that have become part of already chosen
        int key[] = new int[adj.size()];
        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());
            for(List<Integer> l : adj.get(p.getKey())){
                // 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);
                    q.add(new Pair(l.get(0),l.get(1)));
                }
            }
        }
        //for(int i : mstSet) System.out.print(i+" ");
        return Arrays.stream(key).reduce(0,(a,b)->a+b);
    }
}

Enter fullscreen mode Exit fullscreen mode

Top comments (0)