
Asked in Paxcom India
Kruskal’s Minimum Spanning Tree Algorithm Problem Statement
You are given a connected undirected weighted graph. Your task is to determine the weight of the minimum spanning tree of this graph.
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices without any cycles and with the minimum total edge weight. The weight of a spanning tree is the sum of the weights of the edges in that tree.
Input:
The first line contains an integer ‘T’, denoting the number of test cases. Each test case includes:
- The first line contains two integers ‘N’ and ‘M’, representing the number of nodes and edges respectively.
- The subsequent ‘M’ lines each contain three integers ‘U’, ‘V’, and ‘W’, indicating there is an undirected edge between nodes ‘U’ and ‘V’ with weight ‘W’.
Output:
For each test case, return the weight of the minimum spanning tree of the given graph.
Example:
Assume a test case where N = 4, M = 5 and the edges are as follows: [ (1, 2, 10), (2, 3, 15), (3, 4, 4), (1, 4, 5), (2, 4, 6) ]
. The weight of the MST will be 19.
Constraints:
- 1 <= T <= 50
- 1 <= N <= 10000
- 1 <= M <= 10000
- 1 <= W <= 1000
- 1 <= U, V <= N
Time limit: 1 sec
Note:
You don't need to print the output; just implement the function as specified.

The task is to determine the weight of the minimum spanning tree of a given connected undirected weighted graph.
Implement Kruskal's algorithm to find the minimum spanning tree weight.
Sort the edges ba...read more
Interview Questions Asked to Software Engineer at Other Companies
Top Skill-Based Questions for Paxcom India Software Engineer


Reviews
Interviews
Salaries
Users

