Home » Interview coding problems/challenges

Minimum Spanning Tree

Minimum Spanning Tree: This problem has been asked in interview/coding rounds of many top tech companies such as Amazon, Samsung, Flipkart, Microsoft etc.
Submitted by Divyansh Jaipuriyar, on June 16, 2020

Problem statement

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

Input

Given 2 integers N and M. N 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 a, b, w. 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.

Solution Approach

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)

Problem reference: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/practice-problems/algorithm/minimum-spanning-tree-5/