LC 1584 [M] Min Cost to Connect All Points - ALawliet/algorithms GitHub Wiki
Prim's is kinda just like BFS + priority queue
adjacency matrix, searching -> O(V^2)
binary heap and adjacency list -> O(VlogV + ElogV) = O(n2 * logn)
popping from a minheap is O(logn) because the heap must be reordered
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
N = len(points)
adj = {i: [] for i in range(N)} # i : list of [cost, node]
# generate edges
for i in range(N):
x1, y1 = points[i]
for j in range(i+1, N):
x2, y2 = points[j]
dist = abs(x1 - x2) + abs(y1 - y2) # Manhattan dist
adj[i].append([dist, j]) ; adj[j].append([dist, i])
# Prim's: O(n2 * logn)
res = 0
visit = set()
minH = [0,0](/ALawliet/algorithms/wiki/0,0) # [cost, point]
while len(visit) < N:
cost, i = heappop(minH)
if i in visit:
continue
res += cost
visit.add(i)
for neiCost, nei in adj[i]:
if nei not in visit:
heappush(minH, [neiCost, nei])
return res