总成本最低问题，最小生成树 完整代码

总成本最低问题，也称为最小生成树（Minimum Spanning Tree, MST）问题，是一个经典的图论问题，目标是找到一个图中所有顶点之间的边，使得这些边连接成一棵树，并且这棵树的总权重（边的长度或成本）最小。这个问题在计算机科学中有广泛应用，比如网络设计、电路布局等。

在算法上，最著名的解决方法之一是Prim算法和Kruskal算法。Prim算法是从一个起始顶点开始，逐步添加与已选取顶点相连的最短边，直到覆盖所有顶点。而Kruskal算法则是按照边的权重从小到大排序，每次选择当前未加入树中的边中权重最小的一条，直到形成树且不再有连通的边。

下面是使用Python实现的Kruskal算法的示例代码：

import heapq

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

    # 添加边，表示为(u, v, w)
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    # Kruskal's algorithm
    def kruskal_mst(self):
        result = [] # 最小生成树
        i, e = 0, 0 # 初始化计数器
        self.graph = sorted(self.graph, key=lambda item: item) # 按权重排序

        while e < self.V - 1:
            u, v, w = heapq.heappop(self.graph) # 弹出最小的边
            if u not in result and v not in result: # 避免形成环
                e += 1
                result.append([u, v, w])
                i += 1
                print(f"Adding edge {i} with weight {w} ({u}, {v})")

        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.kruskal_mst()
print("Edges of the minimum spanning tree:")
for u, v, w in mst:
    print(f"{u} - {v} with weight {w}")

这个代码首先定义了一个简单的图类，包含了添加边的方法以及Kruskal算法的实现。然后创建一个图实例并添加一些边，最后调用`kruskal_mst`方法得到最小生成树的边及其权重。