最小生成树数据结构考试

### 关于最小生成树的数据结构考试材料

对于准备涉及最小生成树(Minimum Spanning Tree, MST) 数据结构的考试而言，理解其基本概念、算法实现以及应用场景至关重要。MST 是连接图中所有顶点的一个子集，并使得这个子集中边的权重之和尽可能的小[^1]。

#### 定义与性质
最小生成树是从无向连通加权图中选取的一组边构成的新图，该新图保持原图所有的节点相连通的同时使总成本最低。如果一个图有 V 个顶点，则它的任何一棵生成树恰好拥有 V−1 条边。当给定的是带权重的无向图时，可以通过 Kruskal 或 Prim 算法来找到最小生成树。

#### 主要算法介绍
- **Kruskal's Algorithm**: 这种贪心策略按照递增顺序考虑每条边并加入到正在构建中的森林里（只要这样做不会形成环）。为了高效检测循环的存在与否，可以采用 Union-Find 结构。

- **Prim’s Algorithm**: 此方法从任意起点出发逐步扩展已有的部分生成树直到覆盖整个图形；每次迭代都挑选当前未被访问过的最近邻接点作为下一个添加对象。此过程通常借助优先队列优化性能表现。

import heapq

def prim_mst(graph):
    mst = []
    visited = set()
    
    start_vertex = list(graph.keys())[0]
    edges = [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex].items()]
    heapq.heapify(edges)

    while edges:
        weight, u, v = heapq.heappop(edges)
        
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            
            for next_node, w in graph[v].items():
                if next_node not in visited:
                    heapq.heappush(edges, (w, v, next_node))

    return mst

上述代码展示了如何利用 Python 实现 Prim 的最小生成树算法版本之一。这里使用了堆数据结构来进行高效的最小值检索操作。