# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/graph/mst-disjoint-set/minimum-spanning-tree-prims.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.