最小生成树kruskal pta

Kruskal算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）的贪心算法。最小生成树是指在一个带权无向连通图中，选择若干条边，使得任意两点之间有且仅有一条路径，并且所有边的权值之和最小。Kruskal算法通过不断选择最小权值的边，并确保不形成环，直到所有顶点都被连通。

以下是Kruskal算法的基本步骤：

1. **初始化**：将所有边按权值从小到大排序。
2. **选择边**：从权值最小的边开始，选择边并判断是否与已选择的边形成环。如果不形成环，则将该边加入最小生成树。
3. **重复**：重复步骤2，直到所有顶点都被连通，或者选择了n-1条边（n为顶点数）。

Kruskal算法的关键在于如何判断加入一条边后是否形成环。这可以通过并查集（Union-Find）数据结构来实现。

### Kruskal算法的实现步骤

1. **排序边**：将所有边按权值从小到大排序。
2. **初始化并查集**：每个顶点初始时都是一个独立的集合。
3. **选择边并合并集合**：
- 遍历排序后的边，选择权值最小的边。
- 判断这条边的两个顶点是否属于同一个集合。如果不属于，则合并这两个集合，并将这条边加入最小生成树。
4. **重复**：重复步骤3，直到选择了n-1条边，或者所有顶点都被连通。

### 示例代码

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, p):
        while self.parent[p] != p:
            self.parent[p] = self.parent[self.parent[p]]
            p = self.parent[p]
        return p
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            self.parent[rootP] = rootQ
            return True
        return False

def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    mst = []
    
    for edge in edges:
        u, v, w = edge
        if uf.union(u, v):
            mst.append(edge)
            if len(mst) == n - 1:
                break
    
    return mst

# 示例使用
n = 4
edges = [
    (0, 1, 1),
    (0, 2, 2),
    (0, 3, 3),
    (1, 2, 2),
    (1, 3, 1),
    (2, 3, 1)
]

mst = kruskal(n, edges)
print("最小生成树:", mst)

### 解释

1. **UnionFind类**：实现并查集数据结构，用于判断两个顶点是否属于同一个集合。
2. **kruskal函数**：实现Kruskal算法，返回最小生成树。
3. **示例使用**：定义一个图，并调用kruskal函数计算最小生成树。