Q:

# Minimum Spanning Tree

Given a weighted undirected graph. Find the sum of weights of edges of a Minimum Spanning Tree.

Input:

Given 2 integers N and MN represents the number of vertices in the graph. M represents the number of edges between any 2 vertices.

Then M lines follow, each line has 3 space-separated integers abw. Where, a and b represents an edge from a vertex a to a vertex b and w represents the weight of that edge.

Output:

Print the summation of edges weights in the MST.

Examples:

```INPUT:
N = 4, M = 5
1 2 7
1 4 6
4 2 9
4 3 8
2 3 6

OUTPUT:
19, is the sum of edges of MST.```

The problem can be solved with the help of Kruskal and Prim's Algorithm of the minimum spanning tree.

Kruskal Algorithm: Kruskal's algorithm follows the greedy approach in each iteration it adds the weight of the minimum edge to a growing spanning tree.

Following steps are used in Kruskal algo,

• Sort the graph edges on the basis of their weight.
• Add only those edge which doesn't form cycle from minimum weight to maximum edge weight.

C++ Implementation:

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// edge structure for storing edge values.
struct edge {
ll a, b, w;
};

// declare arr with maximum size.
edge arr[100005];

// declare parent array.
ll par[100005];

// declare find function to find.
// parent of current node.
ll find(ll x)
{
// if par[x]==-1 then it is parent.
if (par[x] == -1)
return x;
else
return par[x] = find(par[x]); // path compression.
}

// declare comp function which will help.
// to sort in according to min weight.
bool comp(edge a, edge b)
{
if (a.w < b.w)
return true;
else
return false;
}

// if a and b are with different then.
// join them.
void union1(ll a, ll b)
{
par[b] = a;
}

int main()
{
cout << "Enter N and M: ";
ll n, m;
cin >> n >> m;

for (ll i = 1; i <= n; i++)
par[i] = -1;

cout << "Enter edge and weights:\n";
for (ll i = 0; i < m; i++) {
cin >> arr[i].a >> arr[i].b >> arr[i].w;
}

// initially sum variable as 0.
ll sum = 0;

// sort according to weight.
sort(arr, arr + m, comp);

for (ll i = 0; i < n; i++) {
ll a = arr[i].a;
ll b = arr[i].b;
a = find(a);
b = find(b);
// check if they are already joined.
if (a != b) {
sum += arr[i].w;
union1(a, b);
}
}

cout << "Final sum: ";
cout << sum << "\n";

return 0;
}
``````

Output:

```Enter N and M: 4 5
Enter edge and weights:
1 2 7
1 4 6
4 2 9
4 3 8
2 3 6
Final sum: 19
```

• Time Complexity in worst case is: (nlog(n))
• Space Complexity in worst case is: O(n)