最小生成树克鲁斯卡尔算法数据结构代码

最小生成树算法（Kruskal's algorithm），也称为贪心算法，用于寻找无向图的最小生成树。以下是使用Python实现的克鲁斯卡尔算法的基本数据结构代码：

# 定义边的数据结构，包含两个节点和权重
class Edge:
    def __init__(self, node1, node2, weight):
        self.node1 = node1
        self.node2 = node2
        self.weight = weight

# 边集合，使用列表表示，存储边对象
edges = []

# 图的顶点集合，使用集合表示，存储节点
vertices = set()

def add_edge(edge):
    edges.append(edge)

# Kruskal's algorithm 主函数
def kruskal_mst():
    mst = []  # 存储最小生成树的边
    edges.sort(key=lambda e: e.weight)  # 按照权重排序

    for edge in edges:
        if vertices.union({edge.node1, edge.node2}) == vertices:  # 如果加入这条边不会形成环
            mst.append(edge)
            vertices.add(edge.node1)  # 添加边的一端
            vertices.add(edge.node2)  # 添加边的另一端

    return mst

# 示例用法
add_edge(Edge('A', 'B', 5))
add_edge(Edge('A', 'D', 10))
add_edge(Edge('B', 'C', 4))
add_edge(Edge('C', 'D', 8))
print(kruskal_mst())