Graph Theory37 sections · 1633 units
Open in Course

Min Cost Connect - Implementation

(Prim with lazy heap)

Here is Prim's implementation for connecting points:

visited = array of size n, all false
pq = min-heap
totalCost = 0

pq.push((0, 0))

while pq is not empty:
    (cost, u) = pq.pop()
    if visited[u]:
        continue
    visited[u] = true
    totalCost = totalCost + cost

    for v from 0 to n - 1:
        if not visited[v]:
            dist = |points[u].x - points[v].x| + |points[u].y - points[v].y|
            pq.push((dist, v))

return totalCost

Time: O(n2logn)O(n^2 \log n). Space: O(n)O(n).