在很早之前的文章中，我详细的讲解过什么是最小生成树，以及最小生成树的两种典型算法和算法模版，但是没有给出实际的题目应用，所以可能有的人看了还是不太清楚在遇到什么样的题目时可以使用到最小生成树的算法。
最小生成树。
今天在打卡的时候，恰好遇到了这样一个题目，很典型，基本上很快就能锁定可以使用到最小生成树的算法，下面就结合题目来直观的感受下该算法的应用。
同样的，最小生成树的两种算法我都会详细的给出解题步骤，以及思考过程。
题目链接
题目描述：
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
Kruskal算法
算法三部曲：
- 构造权重边
- 根据权重对边进行排序
- 通过并查集构造最小生成树
代码详解：
class Uf(object):
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def is_connected(self, node1, node2):
return self.find(node1) == self.find(node2)
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 == root2:
return
if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
elif self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
else:
self.parent[root1] = root2
self.rank[root2] += 1
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
if not points:
return 0
n = len(points)
# 根据Kruskal算法三部曲：
# 1、构造权重边：因为Kruskal算法以边为维度，因此需要首先构造所有点两两相连时每条边的权重，在这里就是边的长度。
edges = []
# 这里需要两重循环，但是需要注意，第二层循环需要以第一层循环为起点（两两相连嘛）
for node1 in range(n):
for node2 in range(node1, n):
p1 = points[node1]
p2 = points[node2]
# 这里需要计算权重，也就是边的长度
edge = (node1, node2, abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]))
edges.append(edge)
# 2、排序：对所有的边按照权重从小到大排序（题目要求是最小的花费）
edges.sort(key=lambda item: item[-1])
# 3、生成最小生成树：Kruskal是以并查集算法为基础的，因此这里就是通过并查集来构造联通分量。
uf = Uf(n)
rst = 0
# 因为在第二部的时候，已经将节点按照题目要求排过序了，因此这里直接使用并查集构造联通分量即可
for node1, node2, dest in edges:
if uf.is_connected(node1, node2):
# 如果两个点已经连接了，跳过
continue
# 将花费加入结果中
rst += dest
# 将两个点连接起来
uf.union(node1, node2)
return rst
Prim算法
算法三部曲：
- 统计每个点及其所有相邻点，以及边权重
- 任选一个顶点为源点
- 通过小顶堆构造最小生成树
代码详解：
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
if not points:
return 0
n = len(points)
# 根据Prim算法三部曲：
# 1、构造顶点信息：因为Prim算法以点为维度，因此需要首先统计每个点所有相邻的点及其权重，在这里就是边的长度。
vertexs = defaultdict(list)
# 这里需要两重循环，但是需要注意，第二层循环同样需要以0为起点（因为是要统计每个点所有相邻点）
for node1 in range(n):
for node2 in range(n):
if node1 == node2:
continue
p1 = points[node1]
p2 = points[node2]
# 这里需要计算权重，也就是边的长度
vertexs[str(node1)].append([abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]), node1, node2])
# 2、选择任一源点：这里以0为源点，取出其相邻点列表构造小顶堆
choosed = set('0')
vertexs_info = vertexs['0']
heapify(vertexs_info)
rst = 0
# 3、构造最小生成树：通过每次从小顶堆中取出花费最小的相邻点，然后将该相邻点的所有相邻点加入小顶堆中（这里需要判断该点是否已经选择过了），如此反复，直到堆中数据被取完。
while vertexs_info:
# 从小顶堆中取出花费最小的相邻点信息
dest, ori_vertex, next_vertex = heappop(vertexs_info)
if str(next_vertex) in choosed:
# 如果相邻点已经选择过了，跳过
continue
# 否则，加入已选择列表
choosed.add(str(next_vertex))
# 将花费加入结果中
rst += dest
# 遍历该已选择点的所有相邻点信息
for vertex_info in vertexs[str(next_vertex)]:
if str(vertex_info[2]) in choosed:
# 如果其相邻点选择过，跳过
continue
# 否则，加入小顶堆中。
heappush(vertexs_info, vertex_info)
return rst
评论 (7)
