DSA 克鲁斯卡尔算法
克鲁斯卡尔算法
克鲁斯卡尔算法在无向图中找到最小生成树 (MST) 或最小生成森林。
由克鲁斯卡尔算法找到的 MST（或 MST）是连接所有顶点（或尽可能多）的边的集合，其总边权重最小。
克鲁斯卡尔算法从边权重最小的边开始，将边添加到 MST（或最小生成森林）。
会创建循环的边不会添加到 MST 中。这些是上面动画中的红色闪烁线。
克鲁斯卡尔算法会检查图中的所有边，但上面的动画在完成 MST 或最小生成森林时停止，这样您就不必等待最长的边被检查。
最小生成森林是当一个图有多个最小生成树时的情况。当一个图不连通时会发生这种情况。尝试通过使用上面动画中的复选框自己尝试一下。
与普里姆算法不同，克鲁斯卡尔算法可以用于不连通的图，这意味着它可以找到多个 MST，这就是我们称之为最小生成森林的原因。
为了找出某条边是否会创建循环，我们将在克鲁斯卡尔算法中使用 并查集循环检测。
工作原理
- 将图中的边从最低边权重到最高边权重排序。
- 对于每条边，从边权重最小的边开始
- 这条边会在当前 MST 中创建循环吗？
- 如果没有：将边作为 MST 边添加。
- 这条边会在当前 MST 中创建循环吗？
手动运行
让我们在下面的图上手动运行克鲁斯卡尔算法，以便我们了解详细的逐步操作，然后再尝试编程它。
前三条边被添加到 MST 中。这三条边具有最低的边权重，并且不会创建任何循环
- C-E，权重 2
- D-E，权重 3
- A-B，权重 4
之后，边 C-D（以红色指示）不能添加，因为它会导致循环。
克鲁斯卡尔算法接下来尝试添加到 MST 中的四条边是
- E-G，权重 6
- C-G，权重 7（未添加）
- D-F，权重 7
- B-C，权重 8
边 C-G（以红色指示）不能添加到 MST 中，因为它会导致循环。
如您所见，MST 此时已经创建，但克鲁斯卡尔算法将继续运行，直到测试所有边以查看它们是否可以添加到 MST 中。
克鲁斯卡尔算法接下来尝试添加到 MST 中的最后三条边是具有最高边权重的边
- A-C，权重 9（未添加）
- A-G，权重 10（未添加）
- F-G，权重 11（未添加）
这些边中的每一条都会在 MST 中创建循环，因此它们不能添加。
克鲁斯卡尔算法现在已经完成。
运行下面的模拟以查看克鲁斯卡尔算法正在执行我们刚刚完成的手动步骤。
注意：虽然克鲁斯卡尔算法检查图中的所有边，但此页面顶部的动画在最后一条边被添加到 MST 或最小生成森林后立即停止，这样我们就不必查看所有不能添加的红色边。
这是可能的，因为对于连通图，只存在一个 MST，并且搜索可以在 MST 中的边数比图中的顶点数少一个时停止（\(V-1\)). 对于不连通图，我们的动画中有两个 MST，算法在 MST 的总边数达到 \(V-2\) 时停止。
克鲁斯卡尔算法的实现
为了使克鲁斯卡尔算法能够找到最小生成树 (MST) 或最小生成森林，我们创建了一个 Graph 类。我们将在稍后使用此 Graph 类中的方法来创建来自上面示例的图，并在其上运行克鲁斯卡尔算法。
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 是否在可能的索引值范围内。
为了在克鲁斯卡尔算法中进行并查集循环检测，这两个方法 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 数组来合并（联合）两棵树。rank 数组保存每个根顶点的树高度的粗略估计。在合并两棵树时，排名较低的根将成为另一棵树的根顶点的子节点。
以下是克鲁斯卡尔算法如何在 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 行：在克鲁斯卡尔算法开始尝试将边添加到 MST 之前，必须对边进行排序。
第 40-41 行：parent 和 rank 数组被初始化。一开始，每个顶点都是自己的根（parent 数组中的每个元素都指向自身），每个顶点都没有高度（rank 数组中的 0 值）。
第 44-45 行：选择最小的边，并递增 i 以便在下次迭代中选择正确的边。
第 47-51 行：如果当前边两端的顶点 u 和 v 具有不同的根 x 和 y，这意味着新边不会创建循环，并且会合并这些树。为了合并这些树，当前边被添加到 result 数组中，并且我们运行 union 方法以确保正确合并这些树，这样最终合并的树中就只有一个根顶点。
现在让我们从上面的“手动运行”中创建图并在其上运行克鲁斯卡尔算法
示例
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()克鲁斯卡尔算法的时间复杂度
有关时间复杂度的概括性解释，请访问此页面。
假设图中的边数为 \(E\)，克鲁斯卡尔算法的时间复杂度为
\[ O( E \cdot log{E} ) \]
我们之所以得到这样的时间复杂度，是因为在克鲁斯卡尔算法开始将边添加到最小生成树之前，必须先对这些边进行排序。使用快速算法，例如快速排序或归并排序，仅排序的时间复杂度为 \( O( E \cdot log{E} ) \)。
对边进行排序后，会逐个检查所有边，以判断它们是否会形成环路。如果不会形成环路，则将其添加到最小生成树中。
虽然使用 find 方法检查是否会形成环路以及使用 union 方法将边添加到最小生成树中看起来需要很多工作，但实际上可以将其视为一个操作。原因是此操作大约需要常数时间。这意味着操作所花费的时间随着图的增长而增长非常缓慢，因此实际上不会影响整体时间复杂度。
由于克鲁斯卡尔算法的时间复杂度仅随边数 \(E\) 变化，因此对于稀疏图（边数 \(E\) 与顶点数 \(V\) 之间的比率相对较低）而言，它特别快。
