编写程序实现连通无向图的最小生成树

可以使用Prim算法或Kruskal算法来实现连通无向图的最小生成树。

以下是Prim算法的实现代码：

import heapq

def prim(graph):
    """
    Prim算法实现连通无向图的最小生成树
    :param graph: 无向图，使用邻接矩阵表示，graph[i][j]表示i和j之间的边的权重，如果i和j之间没有边，则为无穷大
    :return: 最小生成树的边集合
    """
    n = len(graph)
    visited = [False] * n  # 记录节点是否已访问
    edges = []  # 存储最小生成树的边集合
    heap = []  # 存储将要访问的节点的堆，每个元素为 (权重, 节点) 的二元组

    # 从第一个节点开始构建最小生成树
    visited[0] = True
    for j in range(n):
        if graph[0][j] != float('inf'):
            heapq.heappush(heap, (graph[0][j], j))

    while heap:
        # 取出堆顶元素，即权重最小的节点
        weight, node = heapq.heappop(heap)

        # 如果该节点已访问，跳过
        if visited[node]:
            continue

        # 将节点标记为已访问
        visited[node] = True
        edges.append((min(node, parent), max(node, parent), weight))  # 将边加入最小生成树的边集合

        # 将与该节点相邻的未访问节点加入堆
        for j in range(n):
            if not visited[j] and graph[node][j] != float('inf'):
                heapq.heappush(heap, (graph[node][j], j))

    return edges

以下是Kruskal算法的实现代码：

def kruskal(graph):
    """
    Kruskal算法实现连通无向图的最小生成树
    :param graph: 无向图，使用邻接矩阵表示，graph[i][j]表示i和j之间的边的权重，如果i和j之间没有边，则为无穷大
    :return: 最小生成树的边集合
    """
    n = len(graph)
    edges = []  # 存储所有边的集合
    for i in range(n):
        for j in range(i + 1, n):  # 只考虑一条边，避免重复
            if graph[i][j] < float('inf'):
                edges.append((i, j, graph[i][j]))

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

    parent = list(range(n))  # 记录每个节点的父节点，用于判断是否形成环
    rank = [0] * n  # 记录每个节点的秩，用于优化

    result = []  # 存储最小生成树的边集合
    for edge in edges:
        u, v, weight = edge

        # 判断该边的两个端点是否已在同一连通分量中
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u == root_v:
            continue

        # 合并两个连通分量
        if rank[root_u] < rank[root_v]:
            parent[root_u] = root_v
        elif rank[root_u] > rank[root_v]:
            parent[root_v] = root_u
        else:
            parent[root_u] = root_v
            rank[root_v] += 1

        result.append(edge)  # 将边加入最小生成树的边集合

    return result

def find(parent, node):
    """
    查找节点的根节点，用于判断两个节点是否已在同一连通分量中
    """
    if parent[node] != node:
        parent[node] = find(parent, parent[node])
    return parent[node]

以上代码均使用了邻接矩阵来表示无向图，如果使用邻接表来表示，则需要对代码进行相应的修改。