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***represents the number of vertices in the graph.*

**N***represents the number of edges between any 2 vertices.*

**M**Then * M* lines follow, each line has 3 space-separated integers

*,*

**a***,*

**b***. Where,*

**w***and*

**a***represents an edge from a vertex*

**b***to a vertex*

**a***and*

**b***represents the weight of that edge.*

**w****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/

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions