什么是克鲁斯卡尔最小生成树算法？
克鲁斯卡尔算法是用来求加权连通图的最小生成树的算法。所谓最小生成树，就是在保证生成树连通的前提下，其边权值之和最小的生成树。本算法按照边权值从小到大的顺序将每条边加入到生成树中，加入时必须保证生成树不形成环。
算法步骤
1) 将图中所有的边按边权从小到大排序；
2) 依次选取权值最小的边，如果这条边的加入对生成树不构成环，则将其加入生成树；
3) 重复步骤2，直至生成树中含有(n-1)条边，其中n为图中节点数。
代码实现
如果我们使用python语言，那么克鲁斯卡尔最小生成树算法的实现如下：
def find(parent, i): if parent[i] == i: return i return find(parent, parent[i])def union(parent, rank, x, y): xroot = find(parent, x) yroot = 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] = 1def kruskal(graph, V): result = [] i, e = 0, 0 graph = sorted(graph, key=lambda item: item[2]) parent = [] rank = [] for node in range(V): parent.append(node) rank.append(0) while e < V - 1: u, v, w = graph[i] i = i 1 x = find(parent, u) y = find(parent, v) if x != y: e = e 1 result.append([u, v, w]) union(parent, rank, x, y) return result
