# Leetcode 1584. Min cost to connect all points

## Prim's algorithms (Mini Heap Queue)

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        graph = [[] for _ in range(n)]

        # 構造相鄰列表 (costs, vertex, source)
        for i in range(n):
            for j in range(i + 1, n):
                costs = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) # 計算節點與節點之間的距離
                graph[i].append([costs,j,i])
                graph[j].append([costs,i,j])
        
        visited = set() # 使用 set 來紀錄節點有無訪問
        heap = [[0,0,0]] # 構造最小堆
        output = 0

        while len(visited) < n: # 訪問直到所有節點訪問完畢
            costs, vertex, source  = heapq.heappop(heap) # 從最小堆中彈出最小邊
            if vertex in visited: # 如果節點已經訪問則跳過
                continue
            print(source, vertex, costs)
            visited.add(vertex) # 把節點加入已訪問
            output += costs
            for costs, vertex, source in graph[vertex]: # 把新訪問節點的所有邊加入最小堆中
                if vertex not in visited: # 如果邊上的節點已經被訪問過，則不加入該邊
                    heapq.heappush(heap,[costs, vertex, source])
        
        return output

## 參考資料

- [Python heapq](https://docs.python.org/zh-tw/3/library/heapq.html)
- [Python 2 solutions kruskal prim standard code clean condcise - Leetcode solution](https://leetcode.com/problems/min-cost-to-connect-all-points/solutions/1476951/python-2-solutions-kruskal-prim-standard-code-clean-concise/)