Q:

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

0

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.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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)

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
<< Given a weighted directed graph, the problem is to...