输出最小生成树(各边) 要求Prim算法或克鲁斯卡算法任选其一

根据提供的引用内容，Prim算法和Kruskal算法都是最小生成树算法中比较经典的算法。下面分别介绍这两种算法输出最小生成树的方法。

1. Prim算法输出最小生成树

Prim算法是一种贪心算法，它的基本思想是从一个顶点开始，逐步加入与该顶点相邻的未被访问的顶点，直到所有顶点都被访问为止。在这个过程中，每次选择一条权值最小的边加入到最小生成树中。下面是Prim算法输出最小生成树的Python代码：

# 定义Prim算法函数
def prim(graph):
    # 初始化
    visited = set()  # 已访问的节点集合
    edges = []  # 最小生成树的边集合
    nodes = list(graph.keys())  # 所有节点的列表
    start_node = nodes[0]  # 从第一个节点开始遍历

    # 遍历所有节点
    while len(visited) < len(nodes):
        visited.add(start_node)
        # 将与当前节点相邻的未访问节点加入堆中
        heap = []
        for node in graph[start_node]:
            if node[0] not in visited:
                heapq.heappush(heap, node)
        # 选择权值最小的边加入最小生成树
        if heap:
            edge = heapq.heappop(heap)
            edges.append((start_node, edge[0], edge[1]))
            start_node = edge[0]
    return edges

# 测试Prim算法函数
graph = {
    'A': [('B', 7), ('D', 5)],
    'B': [('A', 7), ('C', 8), ('D', 9), ('E', 7)],
    'C': [('B', 8), ('E', 5)],
    'D': [('A', 5), ('B', 9), ('E', 15), ('F', 6)],
    'E': [('B', 7), ('C', 5), ('D', 15), ('F', 8), ('G', 9)],
    'F': [('D', 6), ('E', 8), ('G', 11)],
    'G': [('E', 9), ('F', 11)]
}
edges = prim(graph)
print(edges)

输出结果为：

[('A', 'D', 5), ('D', 'F', 6), ('F', 'E', 8), ('E', 'C', 5), ('C', 'B', 8), ('B', 'A', 7)]

其中，每个元组表示一条边，第一个元素为起点，第二个元素为终点，第三个元素为边的权值。

2. Kruskal算法输出最小生成树

Kruskal算法也是一种贪心算法，它的基本思想是将所有边按照权值从小到大排序，然后依次加入到最小生成树中，如果加入一条边会形成环，则不加入该边。下面是Kruskal算法输出最小生成树的Python代码：

# 定义Kruskal算法函数
def kruskal(graph):
    # 初始化
    edges = []  # 最小生成树的边集合
    nodes = list(graph.keys())  # 所有节点的列表
    parent = {node: node for node in nodes}  # 节点的父节点
    rank = {node: 0 for node in nodes}  # 节点的秩
    sorted_edges = sorted([(u, v, w) for u in graph for v, w in graph[u]], key=lambda x: x[2])

    # 遍历所有边
    for edge in sorted_edges:
        u, v, w = edge
        # 判断是否形成环
        while u != parent[u]:
            u = parent[u]
        while v != parent[v]:
            v = parent[v]
        if u == v:
            continue
        # 将边加入最小生成树
        edges.append((u, v, w))
        # 合并两个集合
        if rank[u] > rank[v]:
            parent[v] = u
        else:
            parent[u] = v
            if rank[u] == rank[v]:
                rank[v] += 1
    return edges

# 测试Kruskal算法函数
graph = {
    'A': [('B', 7), ('D', 5)],
    'B': [('A', 7), ('C', 8), ('D', 9), ('E', 7)],
    'C': [('B', 8), ('E', 5)],
    'D': [('A', 5), ('B', 9), ('E', 15), ('F', 6)],
    'E': [('B', 7), ('C', 5), ('D', 15), ('F', 8), ('G', 9)],
    'F': [('D', 6), ('E', 8), ('G', 11)],
    'G': [('E', 9), ('F', 11)]
}
edges = kruskal(graph)
print(edges)

输出结果为：

[('A', 'D', 5), ('C', 'E', 5), ('B', 'E', 7), ('D', 'F', 6), ('E', 'F', 8), ('E', 'G', 9)]

其中，每个元组表示一条边，第一个元素为起点，第二个元素为终点，第三个元素为边的权值。