Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Intermediate Level

Implement the minimumSpanningTreeWeightSimple method that returns the total weight of a minimum spanning tree.

The input represents a weighted undirected graph. nodes is the number of vertices and each edge is given as [u, v, weight].

Your task is to find the total weight of the minimum spanning tree. A minimum spanning tree connects all nodes using the lowest possible total edge weight without creating cycles.

For example, for edges [[0,1,1],[1,2,2],[0,2,4]], choosing weights 1 and 2 connects all three nodes, so the answer is 3.

Example 1
Input:
nodes (int) = 3
edges (int[][]) = [[0,1,1],[1,2,2],[0,2,4]]
size (int) = 3
Return:
(int) 3
Example 2
Input:
nodes (int) = 4
edges (int[][]) = [[0,1,1],[1,2,2],[2,3,3],[0,3,10]]
size (int) = 4
Return:
(int) 6
Example 3
Input:
nodes (int) = 2
edges (int[][]) = [[0,1,5]]
size (int) = 1
Return:
(int) 5

Use Kruskal algorithm.

Sort all edges by weight in ascending order. Then pick edges one by one only when the edge connects two different components. A union-find data structure helps quickly check whether adding an edge would create a cycle.

Stop when nodes - 1 edges have been selected. The accumulated weight is the minimum spanning tree weight.

Pseudocode:

function minimumSpanningTreeWeightSimple(nodes, edges, size):
    sort edges by weight ascending
    parent = create union find for nodes
    totalWeight = 0
    selectedEdges = 0
    for each edge [u, v, weight] in edges:
        if find(u) != find(v):
            union(u, v)
            totalWeight = totalWeight + weight
            selectedEdges++
            if selectedEdges == nodes - 1:
                break
    if selectedEdges != nodes - 1:
        return -1
    return totalWeight
Run your code to see the result.