编写一个程序，实现求解带权连通图中最小生成树的算法

我们可以使用Prim算法或Kruskal算法来求解带权连通图中最小生成树。

以下是Prim算法的Python实现：

import heapq

def prim(graph):
    # 初始化
    mst = {}
    visited = [False] * len(graph)
    heap = [(0, 0)]  # (权重, 节点)

    while heap:
        weight, node = heapq.heappop(heap)
        if visited[node]:
            continue
        visited[node] = True
        mst[node] = weight

        for neighbor, weight in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(heap, (weight, neighbor))

    return mst

其中，graph表示带权连通图，每个节点表示为一个数字，每个节点的邻居表示为一个二元组(邻居节点, 权重)的列表。该算法使用一个最小堆来存储当前所有可用的边，每次从堆中取出权重最小的边，将其加入最小生成树中，并将该边所连接的节点加入堆中。

以下是Kruskal算法的Python实现：

def kruskal(graph):
    # 初始化
    mst = {}
    parent = [i for i in range(len(graph))]
    rank = [0] * len(graph)
    edges = []

    # 将所有边加入堆中
    for node in range(len(graph)):
        for neighbor, weight in graph[node]:
            edges.append((weight, node, neighbor))

    # 根据边的权重排序
    edges.sort()

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            if rank[px] > rank[py]:
                parent[py] = px
            else:
                parent[px] = py
                if rank[px] == rank[py]:
                    rank[py] += 1

    # 遍历所有边，加入最小生成树
    for weight, node1, node2 in edges:
        if find(node1) != find(node2):
            union(node1, node2)
            mst[node1] = weight

    return mst

其中，graph表示带权连通图，每个节点表示为一个数字，每个节点的邻居表示为一个二元组(邻居节点, 权重)的列表。该算法使用并查集来维护当前已连接的节点，每次选择权重最小的边，如果该边的两个节点不在同一个集合中，则将它们连接起来，并将该边加入最小生成树中。