Minimum Spanning Tree (Prims)

Problem Statement

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. Given adjacency list adj as input parameters . Here adj[i] contains vectors of size 2, where the first integer in that vector denotes the end of the edge and the second integer denotes the edge weight.

Example 1:

Input:
3 3
0 1 5
1 2 3
0 2 1

Output:
4
Explanation:

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

Example 2:

Input:
2 1
0 1 5

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

Your task: Since this is a functional problem you don't have to worry about input, you just have to complete the function spanningTree() which takes a number of vertices V and an adjacency list adj as input parameters and returns an integer denoting the sum of weights of the edges of the Minimum Spanning Tree. Here adj[i] contains vectors of size 2, where the first integer in that vector denotes the end of the edge and the second integer denotes the edge weight.

Intuition

Approach 1: Prims

Visit all nodes adjacent to the start node
And Then if not visited, visit them and add distance

Links

https://practice.geeksforgeeks.org/problems/minimum-spanning-tree/1

Video Links

https://www.youtube.com/watch?v=mJcZjjKzeqk&ab_channel=takeUforward

Approach 1:

C++

class Solution
{
	public:
	//Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[]){
                // {edge_wt, {node,parent_node}}
        using pair_not = pair<int,pair<int,int>>;
        priority_queue<pair_not, vector<pair_not>, greater<pair_not>> pq;
        vector<bool> visited (V,false);
        int min_wt = 0;

        pq.push({0,{0,-1}});

        while (!pq.empty()) {
            int wt = pq.top().first;
            int node = pq.top().second.first;
            int parent = pq.top().second.second;
            pq.pop();
            if(!visited[node]){
                visited[node] = true;
                min_wt += wt;
                for(auto &it: adj[node]){
                    int adj_node = it[0];
                    int adj_wt = it[1];
        
                    if(!visited[adj_node])
                        pq.push({adj_wt,{adj_node,node}});
                }
            }
                
        }
        return min_wt;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems