DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

2 1

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)

Great read:

Is it Time to go Back to the Monolith?

History repeats itself. Everything old is new again and I’ve been around long enough to see ideas discarded, rediscovered and return triumphantly to overtake the fad. In recent years SQL has made a tremendous comeback from the dead. We love relational databases all over again. I think the Monolith will have its space odyssey moment again. Microservices and serverless are trends pushed by the cloud vendors, designed to sell us more cloud computing resources.

Microservices make very little sense financially for most use cases. Yes, they can ramp down. But when they scale up, they pay the costs in dividends. The increased observability costs alone line the pockets of the “big cloud” vendors.

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay