Find Min Cost to Connect All Points Leetcode [Python][minHeap][Prim Algo]

We are going to solve below leetcode problem using min Heap based approach.

Question:

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20

from heapq import heappush, heappop

def minCost(points):
    visited = [False for _ in range(len(points))]

    minHeap = []
    heappush(minHeap, [0, 0, points[0]])
    visited = [False for _ in range(len(visited))]
    total_cost = 0

    while not all(visited) and minHeap:
        w, n, point = heappop(minHeap)
        if visited[n]:
            continue
        total_cost += w
        visited[n] = True
        x1, y1 = point

        for i, (x2, y2) in enumerate(points):
            if visited[i]:
                continue
            weight = abs(x2 - x1) + abs(y2 - y1)
            heappush(minHeap, (weight, i, (x2, y2)))
    return total_cost

In above approach, we are picking first point from the list and adding to the minHeap and mark it as visited

Iterate through all other nodes that are not visited and add all those to minHeap:

Now minimum edge that is on top of minHeap is [0,0] — [2,2] edge with a total weight of 4, and mark [2,2] edge as Visited

So, as minimum edge will be on top of minHeap, pop it and add the cost to result and continue this approach until all the nodes are visited.

This way you will end up with result of total cost of minimum spanning Tree using Prim approach.