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
3[[0,1,1],[1,2,2],[0,2,4]]33Example 2
4[[0,1,1],[1,2,2],[2,3,3],[0,3,10]]46Example 3
2[[0,1,5]]15Use 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