图的最小生成树克鲁

克鲁斯卡尔算法是一种用于求解图的最小生成树的贪心算法。它的基本思想是从图中的边集合中选择权重最小的边，并且保证选择的边不会构成环，直到选择了n-1条边为止，其中n是图中顶点的个数。

以下是克鲁斯卡尔算法的步骤：
1. 创建一个空的最小生成树集合MST。
2. 将图中的所有边按照权重从小到大进行排序。
3. 遍历排序后的边集合，依次选择权重最小的边。
4. 如果选择的边不会构成环，则将该边加入MST中。
5. 重复步骤4，直到MST中的边数等于n-1。

下面是一个示例代码，演示了如何使用克鲁斯卡尔算法求解图的最小生成树：

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):
        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 kruskalMST(self):
        result = []
        i = 0
        e = 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 += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

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

        return result


g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

mst = g.kruskalMST()
for u, v, weight in mst:
    print(f"Edge: {u}-{v}, Weight: {weight}")

输出结果为：

Edge: 2-3, Weight: 4
Edge: 0-3, Weight: 5
Edge: 0-1, Weight: 10