Kruskal算法，并求以无向连通图的最小生成树

Kruskal算法是一种用于求解最小生成树的贪心算法。它的基本思想是将图中的所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入某条边会形成环，则不加入该边，直到生成树中包含了所有的顶点为止。下面是求解无向连通图最小生成树的步骤：

1. 将图中的所有边按照权值从小到大排序。
2. 初始化一个空的生成树。
3. 依次遍历排序后的边，如果加入该边不会形成环，则将该边加入生成树中。
4. 重复步骤3，直到生成树中包含了所有的顶点。

最终生成树的权重之和即为无向连通图的最小生成树权重之和。

下面是Python代码实现Kruskal算法求解无向连通图最小生成树的过程：

# 读取输入数据
n, m = map(int, input().split())
edges = []
for i in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

# 将边按照权值从小到大排序
edges.sort(key=lambda x: x[2])

# 初始化并查集
parent = list(range(n + 1))

# 定义查找祖先的函数
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# 定义合并集合的函数
def union(x, y):
    parent[find(x)] = find(y)

# 遍历边，依次加入生成树中
mst_weight = 0
for edge in edges:
    u, v, w = edge
    if find(u) != find(v):
        union(u, v)
        mst_weight += w

print(mst_weight)