# Leetcode 1584. Min Cost to Connect All Points

Leetcode 1584.连接所有点的最小费用

PS：最小生成树有两种算法，本文用的是Prim算法。

# 题目

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.

Example 1:

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

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Constraints:

• 1 <= points.length <= 1000
• -106 <= xi, yi <= 106
• All pairs (xi, yi) are distinct.

# 分析

1.图的所有顶点集合为V；初始令集合u={s},v=V−u={s},v=V−u;
2.在两个集合u,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
3.重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

# 代码

## v1

class Solution(object):
def minCostConnectPoints(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if len(points) < 2:
return 0
n = len(points)
dists = [[None] * n for _ in range(n)]
ret = 0
for i in range(n):
for j in range(i + 1, n):
dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
dists[i][j] = dis
#edges = sorted(edges, key=lambda t:t[0])
s1, s2 = set([0]), set(list(range(1, n)))
#print(edges)
while len(s2) > 0:
e1, e2, d = None, None, None
for i in s1:
for j in s2:
dis = dists[i][j] if i < j else dists[j][i]
if d is None or dis < d:
e1 = i
e2 = j
d = dis
s2.remove(e2)
ret += d
return ret

## v2

class Solution(object):
def minCostConnectPoints(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
import heapq
if len(points) < 2:
return 0
n = len(points)
dists = [[None] * n for _ in range(n)]
ret = 0
for i in range(n):
for j in range(i + 1, n):
dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
dists[i][j] = dis
dists[j][i] = dis
s1, s2 = set([0]), set(list(range(1, n)))
hp = [(dists[0][i], 0, i) for i in range(1, n)]
heapq.heapify(hp)
while len(s2) > 0:
dis, e1, e2 = heapq.heappop(hp)
while e1 in s1 and e2 in s1:
dis, e1, e2 = heapq.heappop(hp)
ret += dis
new_e = e2 if e1 in s1 else e1
s2.remove(new_e)
for e in s2:
dis = dists[new_e][e]
heapq.heappush(hp, (dis, e, new_e))

return ret

done

## v3

class Solution(object):
def minCostConnectPoints(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
n = len(points)

def _dist(i, j):
return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
min_dist = [None] + [_dist(0, i) for i in range(1, n)]

ans = 0
for i in range(1, n):
new_edge_weight = min(filter(lambda x:x is not None, min_dist))
new_node_idx = min_dist.index(new_edge_weight)
ans += new_edge_weight
min_dist[new_node_idx] = None
for i in range(n):
if min_dist[i] is None:
continue
min_dist[i] = min(min_dist[i], _dist(i, new_node_idx))
return ans

done！

——此处是内容的分割线——