python最小生成树测试代码

### 回答1：
下面是一个 Python 最小生成树的示例代码：

import networkx as nx

# 创建一个有 5 个节点，5 条边的无向图
G = nx.Graph()
G.add_edges_from([(1, 2, {'weight': 1}), 
                  (1, 3, {'weight': 3}), 
                  (1, 4, {'weight': 4}), 
                  (2, 3, {'weight': 2}), 
                  (3, 4, {'weight': 5}), 
                  (4, 5, {'weight': 2}), 
                  (2, 5, {'weight': 4})])

# 计算最小生成树
T = nx.minimum_spanning_tree(G)

# 输出最小生成树的边权和
print(sum([e[2]['weight'] for e in T.edges(data=True)]))

这段代码会创建一个带权的无向图，然后使用 `networkx` 库的 `minimum_spanning_tree()` 函数计算最小生成树，最后输出最小生成树的边权和。

希望这个例子能帮到你。

### 回答2：
下面是一个使用Python实现最小生成树算法（Prim算法）的示例代码：

from queue import PriorityQueue


def prim(graph):
    # 记录已访问的顶点
    visited = set()

    # 使用优先队列存储边
    edges = PriorityQueue()

    # 任选一个起始顶点
    start_vertex = list(graph.keys())[0]

    # 将起始顶点标记为已访问
    visited.add(start_vertex)

    # 将该顶点的所有边加入优先队列
    for edge in graph[start_vertex]:
        edges.put(edge)

    # 最小生成树的代价
    cost = 0

    # 选择n-1条边
    while len(visited) < len(graph):
        # 取出优先队列中代价最小且连接到已访问顶点的边
        edge = edges.get()
        vertex1, vertex2, weight = edge

        # 若边的两个顶点都已访问，则跳过
        if vertex1 in visited and vertex2 in visited:
            continue

        # 将边的另一个顶点标记为已访问
        if vertex1 in visited:
            visited.add(vertex2)
        else:
            visited.add(vertex1)

        # 将该顶点的所有边加入优先队列
        for neighbor in graph[vertex2]:
            edges.put(neighbor)

        cost += weight

    return cost


# 测试代码
if __name__ == "__main__":
    # 以字典形式存储图的边
    graph = {
        'A': [('B', 2), ('C', 3)],
        'B': [('A', 2), ('C', 1), ('D', 1)],
        'C': [('A', 3), ('B', 1), ('D', 3)],
        'D': [('B', 1), ('C', 3)]
    }

    # 计算最小生成树的代价
    min_cost = prim(graph)

    print("最小生成树的代价:", min_cost)

该示例代码中的`prim`函数实现了Prim算法，通过优先队列来存储边并选择代价最小的边进行扩展。示例中以字典的形式存储了图的边，其中键为顶点，值为该顶点与其他顶点的连边和权重。通过调用`prim`函数，可以计算出给定图的最小生成树的代价，并打印输出。

### 回答3：
Python最小生成树测试代码一般使用Prim算法或Kruskal算法来实现。以下是一个使用Prim算法的示例代码：

# 导入图相关的库
from collections import defaultdict
import heapq

# 定义图类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 图的顶点个数
        self.graph = defaultdict(list)  # 使用defaultdict创建邻接列表

    # 添加边
    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))

    # Prim算法实现最小生成树
    def prim_mst(self):
        visited = [False] * self.V  # 存储节点是否已被访问
        min_heap = []  # 使用最小堆来选择下一个节点
        start_vertex = 0  # 从节点0开始
        mst = []  # 存储最小生成树的边

        # 将起始节点添加到最小堆中
        heapq.heappush(min_heap, (0, start_vertex))

        while min_heap:
            weight, vertex = heapq.heappop(min_heap)  # 选取最小权重的边
            if visited[vertex]:
                continue
            visited[vertex] = True
            mst.append((weight, vertex))

            # 遍历当前节点的邻接节点
            for neighbor, neighbor_weight in self.graph[vertex]:
                if not visited[neighbor]:
                    heapq.heappush(min_heap, (neighbor_weight, neighbor))

        return mst

# 测试代码
if __name__ == '__main__':
    g = Graph(5)
    g.add_edge(0, 1, 2)
    g.add_edge(0, 3, 6)
    g.add_edge(1, 2, 3)
    g.add_edge(1, 3, 8)
    g.add_edge(1, 4, 5)
    g.add_edge(2, 4, 7)
    g.add_edge(3, 4, 9)
  
    mst = g.prim_mst()
    print("Prim算法生成的最小生成树边：")
    for weight, vertex in mst:
        print(f"边 {vertex} - {vertex+1}，权重：{weight}")

这段代码创建了一个表示图的类`Graph`，其中使用邻接列表表示图的边。`prim_mst`方法使用Prim算法来生成最小生成树。测试代码中创建了一个图并调用`prim_mst`方法来打印最小生成树的边。