Build all edges (complete graph), then run Kruskal:
def minCostConnectPoints(points):
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((dist, i, j))
edges.sort()
uf = UnionFind(n)
cost = 0
edgesUsed = 0
for dist, u, v in edges:
if uf.union(u, v):
cost += dist
edgesUsed += 1
if edgesUsed == n - 1:
break
return cost
Time: — edges, sort.
For large , Prim's algorithm with a heap is faster on dense graphs.