最小生成树python 以及运行结果图

最小生成树（Minimum Spanning Tree, MST）是指在一个加权无向图中找到一棵包含所有顶点的树，其总边权重尽可能小。在Python中，我们可以使用多种数据结构和算法来求解最小生成树，其中一种常见的方法是Prim算法或Kruskal算法。

**Prim算法**：

import heapq

def prim(graph, start):
    mst = {} # 存储MST边及其权重
    visited = {start: 0} # 标记已访问节点及到起点的距离
    unvisited = set(graph.keys()) - {start}
    while unvisited:
        min_edge = None
        for node in unvisited:
            if node in visited and (min_edge is None or visited[node] + graph[node][start] < min_edge[1]):
                min_edge = (node, visited[node] + graph[node][start])
        u, weight = min_edge
        if u not in mst:
            mst[u] = weight
        del visited[u]
        unvisited.remove(u)
    return mst

# 示例图表示法，字典格式，如 {'A': {'B': 5, 'D': 1}, 'B': {'A': 5, 'C': 4, 'D': 2}, 'C': {'B': 4, 'D': 6}, 'D': {'A': 1, 'B': 2, 'C': 6}}
graph = {...}
start_node = 'A'
mst_dict = prim(graph, start_node)

**Kruskal算法**：

from collections import defaultdict

def kruskal(graph):
    mst = []
    edges = [(weight, edge) for edge, weight in graph.items()]
    edges.sort()
    forest = defaultdict(set)  # 用于存储每个连通分量
    for weight, edge in edges:
        u, v = edge
        forest[u].add(v)
        forest[v].add(u)
        if len(forest[u]) == len(forest[v]):  # 如果两个集合大小相等，合并成一个连通分量
            mst.append(edge)
            forest.pop(u)
            forest.pop(v)
    return mst

# 使用示例同上
kruskal_mst = kruskal(graph)

运行结果图通常是以树的形式表示，每条边都代表最小生成树的一段连接，并附带该边的权重。在上述代码中，`mst_dict` 或 `kruskal_mst` 就会是一个键值对的列表或字典，其中键是顶点，值是到其他顶点的最小边权。