> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/graph/mst-disjoint-set/minimum-spanning-tree-prims.md).

# 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:**

<pre><code><strong>Input:
</strong>3 3
0 1 5
1 2 3
0 2 1

<strong>Output:
</strong>4
<strong>Explanation:
</strong>
The Spanning Tree resulting in a weight
of 4 is shown above.
</code></pre>

**Example 2:**

<pre><code><strong>Input:
</strong>2 1
0 1 5

<strong>Output:
</strong>5
<strong>Explanation:
</strong>Only one Spanning Tree is possible
which has a weight of 5.
</code></pre>

&#x20;

**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>\ <br>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
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;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###