DSA Kruskal 算法
Kruskal 算法
Kruskal 算法查找无向图中的最小生成树 (MST)，或最小生成森林。
Kruskal 算法找到的 MST（或 MSTs）是连接所有顶点（或尽可能多）且总边权重最小的边集。
Kruskal 算法按从小到大的边权重顺序添加边到 MST（或最小生成森林）。
会形成环的边不会被添加到 MST 中。这些是上面动画中的红色闪烁线。
Kruskal 算法会检查图中的所有边，但上面的动画会在 MST 或最小生成森林完成时停止，这样您就不必等待最长的边被检查。
最小生成森林 当图中存在多个最小生成树时，就称之为最小生成森林。当图不连通时就会发生这种情况。在上面的动画中，您可以尝试通过使用复选框来验证这一点。
与 Prim 算法不同，Kruskal 算法可用于不连通的图，这意味着它可以找到多个 MST，这就是我们称之为最小生成森林的原因。
为了确定一条边是否会形成环，我们将在 Kruskal 算法中使用 并查集（Union-Find）环检测。
工作原理
- 将图中的边按从小到大的边权重排序。
- 对于每条边，从权重最小的边开始
- 这条边会在当前的 MST 中形成环吗？
- 如果否：将边添加为 MST 边。
- 这条边会在当前的 MST 中形成环吗？
手动演练
让我们在下面的图上手动运行 Kruskal 算法，以便在尝试编程之前理解详细的逐步操作。
前三条边被添加到 MST 中。这三条边具有最小的边权重且不形成任何环。
- C-E，权重 2
- D-E，权重 3
- A-B，权重 4
之后，边 C-D（图中红色标出）无法添加，因为它会形成一个环。
Kruskal 算法接下来尝试添加到 MST 的四条边是：
- E-G，权重 6
- C-G，权重 7（未添加）
- D-F，权重 7
- B-C，权重 8
边 C-G（图中红色标出）无法添加到 MST，因为它会形成一个环。
正如您所见，此时 MST 已经创建完成，但 Kruskal 算法将继续运行，直到所有边都被测试是否可以添加到 MST 中。
Kruskal 算法尝试添加到 MST 的最后三条边是边权重最高的边：
- A-C，权重 9（未添加）
- A-G，权重 10（未添加）
- F-G，权重 11（未添加）
这些边中的每一条都会在 MST 中形成一个环，所以它们无法添加。
Kruskal 算法现在已完成。
运行下面的模拟，查看 Kruskal 算法如何执行我们刚刚完成的手动步骤。
注意： 尽管 Kruskal 算法会检查图中的所有边，但此页面顶部的动画会在添加完最后一条 MST 或最小生成森林的边后立即停止，这样我们就不必查看所有无法添加的红色边。
这是可能的，因为对于连通图，只有一个 MST，并且当 MST 中的边数比图中的顶点数少 1 时（\(V-1\)），搜索就可以停止。对于不连通的图，我们的动画中有两个 MST，当 MST 的总边数达到 \(V-2\) 时，算法会停止。
Kruskal 算法的实现
为了让 Kruskal 算法找到最小生成树 (MST) 或最小生成森林，我们创建一个 Graph 类。稍后我们将使用这个 Graph 类中的方法来从上面的示例创建图，并在其上运行 Kruskal 算法。
class Graph:
def __init__(self, size):
self.size = size
self.edges = [] # For storing edges as (weight, u, v)
self.vertex_data = [''] * size # Store vertex names
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.edges.append((weight, u, v)) # Add edge with weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 8 行和第 12 行： 检查输入参数 u、v 和 vertex 是否在可能的索引值范围内。
为了在 Kruskal 算法中进行并查集环检测，这两个方法 find 和 union 也在 Graph 类中定义。
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1第 15-18 行： find 方法使用 parent 数组递归查找顶点的根。对于每个顶点，parent 数组保存一个指向该顶点父节点的指针（索引）。当 find 方法找到 parent 数组中指向自身的一个顶点时，就找到了根顶点。请继续阅读，了解 find 方法和 parent 数组如何在 kruskals_algorithm 方法中使用。
第 20-29 行： 当一条边被添加到 MST 时，union 方法使用 parent 数组来合并（union）两个树。 rank 数组保存了每个根顶点的树高度的粗略估计。合并两棵树时，秩较低的根会成为另一棵树的根节点的子节点。
以下是 Kruskal 算法作为 Graph 类中的方法实现的方式：
def kruskals_algorithm(self):
result = [] # MST
i = 0 # edge counter
self.edges = sorted(self.edges, key=lambda item: item[2])
parent, rank = [], []
for node in range(self.size):
parent.append(node)
rank.append(0)
while i < len(self.edges):
u, v, weight = self.edges[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
result.append((u, v, weight))
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, weight in result:
print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")第 35 行： Kruskal 算法在尝试将边添加到 MST 之前，必须先对边进行排序。
第 40-41 行： 初始化 parent 和 rank 数组。开始时，每个顶点都是自己的根（parent 数组中的每个元素都指向自身），并且每个顶点的初始高度为 0（rank 数组中的值为 0）。
第 44-45 行： 选择最小的边，并将 i 加 1，以便在下一次迭代中选择正确的边。
第 47-51 行： 如果当前边的两个端点 u 和 v 具有不同的根 x 和 y，则表示新边不会形成环，并且将合并这两个树。为了合并树，当前边被添加到 result 数组中，然后运行 union 方法以确保树被正确合并，从而使合并后的结果树只有一个根顶点。
现在，让我们创建“手动运行”上面显示的图，并在其上运行 Kruskal 算法。
示例
Python
class Graph:
def __init__(self, size):
self.size = size
self.edges = [] # For storing edges as (weight, u, v)
self.vertex_data = [''] * size # Store vertex names
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.edges.append((u, v, weight)) # Add edge with weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskals_algorithm(self):
result = [] # MST
i = 0 # edge counter
self.edges = sorted(self.edges, key=lambda item: item[2])
parent, rank = [], []
for node in range(self.size):
parent.append(node)
rank.append(0)
while i < len(self.edges):
u, v, weight = self.edges[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
result.append((u, v, weight))
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, weight in result:
print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(0, 1, 4) #A-B, 4
g.add_edge(0, 6, 10) #A-G, 10
g.add_edge(0, 2, 9) #A-C, 9
g.add_edge(1, 2, 8) #B-C, 8
g.add_edge(2, 3, 5) #C-D, 5
g.add_edge(2, 4, 2) #C-E, 2
g.add_edge(2, 6, 7) #C-G, 7
g.add_edge(3, 4, 3) #D-E, 3
g.add_edge(3, 5, 7) #D-F, 7
g.add_edge(4, 6, 6) #E-G, 6
g.add_edge(5, 6, 11) #F-G, 11
print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()Kruskal 算法的时间复杂度
有关时间复杂度的一般性解释，请访问此页面。
令 \(E\) 为图中边的数量，Kruskal 算法的时间复杂度为：
\[ O( E \cdot log{E} ) \]
我们得到这个时间复杂度是因为在 Kruskal 开始添加边到 MST 之前，必须先对边进行排序。使用像 快速排序 或 归并排序 这样的快速排序算法，仅此排序本身的时间复杂度为 \( O( E \cdot log{E} ) \)。
在对边进行排序之后，它们会逐一被检查，以确定是否会形成环，如果不会，则将其添加到 MST 中。
尽管使用 find 方法检查环的创建以及使用 union 方法将边包含到 MST 中看起来工作量很大，但这些仍然可以视为一个操作。之所以可以将它们视为一个操作，是因为它们花费的时间大约是常数时间。这意味着此操作所需的时间随着图的增长而增长非常缓慢，因此实际上不会影响整体时间复杂度。
由于 Kruskal 算法的时间复杂度仅随边的数量 \(E\) 而变化，因此它对于稀疏图（其中边数 \(E\) 与顶点数 \(V\) 的比率相对较低）尤其快速。
