克鲁斯卡尔算法代码编写

以下是克鲁斯卡尔算法的Python实现：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        x_root = self.find(parent, x)
        y_root = self.find(parent, y)

        if rank[x_root] > rank[y_root]:
            parent[y_root] = x_root
        elif rank[x_root] < rank[y_root]:
            parent[x_root] = y_root
        else:
            parent[y_root] = x_root
            rank[x_root] += 1

    def kruskal(self):
        result = []
        i, e = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

在这个实现中，我们首先定义了一个Graph类，它包含一个构造函数和三个方法：add_edge()、find()和union()。add_edge()方法用于向图中添加一条边。find()方法和union()方法是用于并查集的，它们用于查找节点所在的集合和将两个集合合并。

kruskal()方法是主要算法实现。它首先将所有边按权重排序，然后依次考虑每一条边。对于每条边，我们查找它所连接的两个节点所在的集合，如果这两个节点不在同一个集合中，我们就将它们合并，并将这条边加入最小生成树中。最后，kruskal()方法返回最小生成树的所有边。