使用Graph()在Python中计算图的最小生成树

在Python中，我们可以使用Graph()类来表示一个图，并计算图的最小生成树。最小生成树是指连接图中所有节点的子图，并且权重之和最小。

下面是一个使用Graph()类计算图的最小生成树的例子：

from collections import defaultdict
import heapq

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))

    def prim(self, start):
        # 初始化最小生成树
        mst = []
        # 保存节点与权重的键值对，用于优化查找最小权重节点的时间复杂度
        heap = [(0, start)]
        # 保存已经访问过的节点
        visited = set()

        while heap:
            weight, node = heapq.heappop(heap)
            # 如果节点已经访问过，则继续下一次循环
            if node in visited:
                continue
            # 将节点标记为已访问
            visited.add(node)
            # 将节点添加到最小生成树中
            mst.append((node, weight))

            for neighbor, edge_weight in self.graph[node]:
                # 如果邻居节点没有访问过，则将其加入堆中
                if neighbor not in visited:
                    heapq.heappush(heap, (edge_weight, neighbor))

        return mst


# 创建一个图对象
g = Graph()
# 添加边
g.add_edge('A', 'B', 1)
g.add_edge('A', 'C', 4)
g.add_edge('B', 'C', 2)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 1)

# 计算最小生成树
mst = g.prim('A')

# 打印最小生成树
for node, weight in mst:
    print(f'{node} - {weight}')

在上面的例子中，我们首先创建了一个Graph类，其中包含了添加边和计算最小生成树的方法。在添加边的过程中，我们使用了一个defaultdict来保存节点之间的连接关系。然后，在prim方法中，我们使用了一个最小堆来保存边的权重，并通过优化查找最小权重节点的时间复杂度。

我们使用上面的例子来演示了如何使用Graph()类进行最小生成树的计算。首先，我们创建了一个图对象g，并通过调用add_edge方法添加了一些边。然后，我们调用prim方法来计算最小生成树，并将结果保存在变量mst中。最后，我们遍历mst并打印出最小生成树的节点和权重。

运行上述代码，输出为：

A - 0
B - 1
C - 2
D - 1

这表示计算得到的最小生成树为A-B-C-D，对应的权重之和为4.