Minimum Spanning Tree (MST) | Prims Algorithm

Spanning Tree

A tree in which we have N nodes and N-1 edges and all nodes are reachable from each other.

Some of the possible Spannig trees

Minimum Spanning Tree

A spanning tree where the total sum of all the edges is the smallest possible is called a minimum spanning tree.

There are 2 algorithms to find the mimum spanning tree from a given graph

• Prims Algorithm

• Krushkals Algorithm

Prims Algorithm

Given a weighted, undirected, and connected graph with V vertices and E edges, your task is to find the sum of the weights of the edges in the Minimum Spanning Tree (MST) of the graph. The graph is provided as a list of edges, where each edge is represented as [u, v, w], indicating an edge between vertex u and vertex v with edge weight w.

Input: V = 3, E = 3, Edges = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]

Output: 4
Explanation:

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

Input: V = 2, E = 1, Edges = [[0 1 5]]

Output: 5 
Explanation: Only one Spanning Tree is possible which has a weight of 5.

Solution

• Prim's Algorithm builds the Minimum Spanning Tree (MST) by choosing the edge with the smallest weight that connects a new vertex to the growing MST.

• It follows a greedy approach, making the most cost-effective choice at each step.

• If another necessary node needs to be connected, it can be easily added since it's already in the queue.

• The algorithm uses a priority queue implemented as a min-heap to efficiently select the next minimum weight edge.

• This ensures the MST is constructed with the least possible total edge weight.

Time - O(E logE) + O(E logE)

Space - O(E)

Note: It's not necessary to store the parent with the triplet, but if we want to know the exact edges of the minimum spanning tree, it can be helpful.

class Solution {

    class Triplet{
        int dist;
        int node;
        int parent;

        Triplet(int dist, int node, int parent){
            this.dist = dist;
            this.node = node;
            this.parent = parent;
        }

        @Override
        public String toString(){
            return "dist="+dist+" node="+node + " parent="+parent;
        }
    }

    public int spanningTree(int V, int[][] edges) {
        List<List<List<Integer>>> adjList = createAdjList(V, edges);
        Queue<Triplet> queue = new PriorityQueue<>((triplet1, triplet2) -> triplet1.dist - triplet2.dist);

        int[] visited = new int[V];

        queue.add(new Triplet(0, 0, -1));
        int sum = 0;

        while(!queue.isEmpty()){
            // System.out.println("queue : " + queue);
            Triplet triplet = queue.poll();

            int vertex = triplet.node;
            int dist = triplet.dist;

            if(visited[vertex] == 1) continue;

            visited[vertex] = 1;
            sum += dist;

            for(List<Integer> neighbour : adjList.get(vertex)){
                int neighbourNode = neighbour.get(0);
                int neighbourDist = neighbour.get(1);
                if(visited[neighbourNode]!=1){
                    queue.add(new Triplet(neighbourDist, neighbourNode, vertex));
                }
            }
        }

        return sum;

    }

    private List<List<List<Integer>>> createAdjList(int V, int[][] edges){
        List<List<List<Integer>>> adjList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjList.add(new ArrayList<>());
        }

        for(int[] neighbour : edges){
            adjList.get(neighbour[0]).add(List.of(neighbour[1], neighbour[2]));
            adjList.get(neighbour[1]).add(List.of(neighbour[0], neighbour[2]));
        }

        return adjList;
    }
}