最小生成树
最小生成树是图论的算法之一，用于解决带有权重且无环的最小连通问题。我们要计算连通所有节点的最小值，如果定义连通无向图
G
=
(
V
,
E
)
G=(V,E)
G=(V,E), 其中，
V
和
E
V和E
V和E分别表示节点和节点所有的可能连接。对于每条边
(
u
,
v
)
∈
E
(u, v)∈E
(u,v)∈E，都赋予权重
w
=
(
u
,
v
)
w=(u,v)
w=(u,v)，作为连接节点u和节点v的代价。希望找到一个无环子集
T
⊆
E
T\\subseteq{E}
T⊆E,即能够将所有节点连接起来，又具有最小权重，也即
w
(
T
)
=
∑
(
u
,
v
)
∈
T
w
(
u
,
v
)
w(T)=\\sum\\limits_{(u,v)\\in{T}}{w(u,v)}
w(T)=(u,v)∈T∑w(u,v),很显然，无环子集T是一棵树，因为T是由图G生成的，求取该生成树的问题为最小生成问题。
如下所示： 
接下来将使用两种贪心算法，分别为Kruskal和Prim算法，找到最小生成树T（最小生成树并不唯一）。在介绍两种算法之前，先介绍安全边和 安全边：A是某棵树的最小生成树的一个子集，如果边（u, v）加入到集合A中，如果
A
∪
(
u
,
v
)
A\\cup{(u,v)}
A∪(u,v)也是某棵树的最小生成树的子集，由于可以安全地将边(u,v)加入到集合A而不会破坏集合A的循环不变式，称这样的边为安全边。
切割：对于无向图
G
=
(
V
,
E
)
G = (V,E)
G=(V,E)的一个切割
(
S
,
V
−
S
)
(S, V-S)
(S,V−S)是集合V 的一个划分，如果某一条边（u，v）的一个端点位于集合S，而另一个端点位于集合V-S，那么就称该条边横跨切割(S,V-S)。如果集合A中不存在横跨该切割的边，称该切割尊重集合A。在横跨一个切割的所有边中，权重最小的边称为轻量级边。示意图如下所示： 
定理1：如果集合A为某个连通无向图
G
=
(
V
,
E
)
G=(V,E)
G=(V,E)的一个子集，且边E定义了实数权重函数w。A包括在图G的某棵最小生成树中，设（S,V-S）是图G中尊重集合A的任意一个切割，又设（u，v）是横框切割（S,V-S）的一条轻量级边，那么边（u，v）对于集合A是安全的。也就是说，找到某个尊重集合A的切割中的轻量级边，将该轻量级边加入到集合A中，集合A仍然是安全的。
Kruskal算法和Prim算法都是对找到安全边的细化。对于Kruskal算法，集合A是一个森林，节点就是给定图的节点。对于Prim算法，结合A则是一颗树，每次加入到A中的安全边永远是连接A和A之外某个节点的边中权重最小的边。可以发现，Kruskal和Prim算法都是贪心算法。接下来将对两个算法详细介绍。
Kruskal算法
Kruskal找到安全边的方法是，在所有连接森林中两颗不同树的边里面，找到权重最小的那一条边
（
u
，
v
）
（u，v）
（u，v）。假设C1和C2为边（u，v）所连接的两棵树，由于边（u，v）一定是连接C1和某棵树的轻量级边，由定理1可以推出，边（u，v）是C1的一条安全边。
模板
def kruskal(edges:List[List[int]], n:int , m: int) –>:
# n个节点，m条边
# edges存储的格式为：edge[i] = [w,u,v],u和v分别为两个端点，w为权重
edges.sort(key lambda x: x[0])
parent = [i for i in range(n)]
def find(x):
if x != fa[x]:
parent[x] = find(parent[x])
return parent[x]
def union(x,y):
parent[find(x)] = find(y)
ans = 0
mst_edges = []
for w, u, v in edges:
# 如果 u 和 v 是不连通的，那么权重最小的切割w对于find(u)是安全的
if find(u) != find(v):
union(u,v)
ans += w
mst_edges.append((u,v,w))
return ans
Kruskal算法流程示意图： 
Prim算法
集合A中的边总是构成一颗树，从树中的任意一个节点r开始，一直长大到覆盖V中的所有节点为止。在连接集合A和集合A之外任意节点的所有边中，选择一条轻量级边加入到集合A中。
def prim(edges, n,m) :
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v,w))
graph[v].append((u,w))
visited = [False] * n
min_heap = [(0,–1,0)]
#创建优先队列，格式为：(权重，当前节点，当前边终点)，以权重作为首先排序，从节点0开始
ans = 0
mst_edges = []
while min_heap and len(mst_edges) < n – 1:
# 每次弹出的边，都是当前权重最小的边，并且以节点 0 作为起始节点
w,u,v = heapq.heappop(min_heap)
if visited[v]:
continue
visited[v] = True
ans += w
# 如果 u == -1 ，说明不是起点
if u != –1:
mst_edegs.append((u,v,w))
# v是新加入到 最小生成树的终点，遍历 v 的所有邻边
for next_node, weight in graph[v]:
if not visited[next_node]:
# 如果 next_node 没有加入生成树，那么这条边就是候选边,加入到最小堆中
heap.heanppush(heap, (weight, v, next_node))
if len(mst_edges) != n – 1:
return –1, []
return ans, mst_edges
Prim算法流程示意图 
相关题目
1584.连接所有点的最小费用
1584. 连接所有点的最小费用 – 力扣（LeetCode） 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi – xj| + |yi – yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
示例 1：
**输入：**points = [[0,0],[2,2],[3,10],[5,2],[7,0]] **输出：**20 解释： 
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。 注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：
**输入：**points = [[3,12],[-2,5],[-4,1]] **输出：**18
示例 3：
**输入：**points = [[0,0],[1,1],[1,0],[-1,1]] **输出：**4
示例 4：
**输入：**points = [[-1000000,-1000000],[1000000,1000000]] **输出：**4000000
示例 5：
**输入：**points = [[0,0]] **输出：**0
提示：
- 1 <= points.length <= 1000
- -106 <= xi, yi <= 106
- 所有点 (xi, yi) 两两不同。
import heapq
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) –> int:
# Prim解法
dist = lambda x,y: abs(points[x][0] – points[y][0]) + abs(points[x][1] – points[y][1])
n = len(points)
edges = []
mst_edges = []
graph = [[]for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
edges.append((dist(i,j),i,j))
for w,u,v in edges:
graph[u].append((v,w))
graph[v].append((u,w))
visited = [False] * n
min_heap = [(0, –1, 0)]
ans = 0
while min_heap and len(mst_edges) < n – 1:
w, u, v = heapq.heappop(min_heap)
if visited[v]:
continue
visited[v] = True
ans += w
if u != –1:
mst_edges.append((w,u,v))
for next_node, weight in graph[v]:
heapq.heappush(min_heap,(weight, v, next_node))
if len(mst_edges) != n – 1:
return ans, []
return ans
## Kruskal 解法
# n = len(points)
# ans = 0
# edges = []
# mst_edges = []
# parent = list(range(n))
# def find(x):
# if parent[x] != x:
# parent[x] = find(parent[x])
# return parent[x]
# def union(x, y):
# parent[find(y)] = find(x)
# # 自己构造 edges
# dist = lambda x,y: abs(points[x][0] – points[y][0]) + abs(points[x][1] – points[y][1])
# for i in range(n):
# for j in range(i + 1, n):
# edges.append((dist(i, j), i, j))
# # 需要对权重值进行排序
# edges.sort()
# for w, u, v in edges:
# if find(u) != find(v):
# union(u, v)
# ans += w
# mst_edges.append((w, u, v))
# return ans
