networkx的minimum_spanning_tree()可直接求最小生成树，默认Kruskal算法，支持Prim切换；输入需为无向图，权重字段默认'weight'，不连通时返回最小生成森林。
怎么用 networkx 快速求最小生成树（不手写）
绝大多数实际场景下，别自己实现 Kruskal 或 Prim——networkx 的 minimum_spanning_tree() 已经封装好，正确、稳定、支持多种图类型。
它默认用 Kruskal（并查集 + 边排序），对稀疏图友好；加参数 algorithm='prim' 可切到 Prim（优先队列），适合稠密图。内部自动处理有向/无向、权重缺失、连通性检查等边界。
- 输入图必须是
networkx.Graph（无向），有向图会静默转为无向，可能不是你想要的 - 边权必须存在且为数值，字段名默认是
'weight'；如果用的是'cost'，得传weight='cost' - 图不连通时，返回的是「最小生成森林」（多个树组成的子图），不是报错——容易误以为算错了
- 示例：
import networkx as nx<br>G = nx.Graph()<br>G.add_weighted_edges_from([(0,1,2), (1,2,3), (0,2,4)])<br>mst = nx.minimum_spanning_tree(G) # 返回新 Graph 对象
Kruskal 手写要注意哪些关键点
核心就三步：边排序 → 并查集判环 → 累加边。最容易翻车的是并查集没路径压缩，或排序后没去重边，导致时间退化到 O(E²)。
- 边必须按权重升序，但 Python 的
sorted(edges, key=lambda x: x[2])要确保第三项是权重，索引错就全乱了 - 并查集的
find必须带路径压缩，否则多次union-find后效率骤降；union建议按秩合并，非必需但更稳 - 图含自环或重边时，
Kruskal本身能跳过自环，但重边若权重不同，排序后自然取最小的——这点常被忽略，以为要预处理去重 - 错误现象：
RecursionError（find 没压缩）、MST 边数少于n-1（漏判连通性）、结果权重偏大（排序字段搞反）
Prim 用堆实现时为什么老出错
本质是维护「已选点集」到「未选点集」的最短边。Python 用 heapq 实现时，常见问题是把过期的边留在堆里没清理，导致重复加点或权重不准。
立即学习“Python免费学习笔记（深入）”；
- 不能只靠
heappop就信这个边有效——得配一个布尔数组in_mst[]或集合记录已加入点，每次 pop 后先检查是否已处理 - 初始化要把起点所有邻边推入堆；如果图用邻接表存，注意遍历的是
graph[start]，不是graph[node]（node 还没定义） - 权重类型必须一致：混用
int和float可能触发TypeError；None权重会导致堆比较失败 - 性能陷阱：用列表找最小边（
O(V)）代替堆（O(log V)），小图看不出来，点一多就卡死
稀疏图 vs 稠密图：怎么选算法不踩坑
理论复杂度上，Kruskal 是 O(E log E)，Prim（堆版）是 O(E log V)。但实际选哪个，得看图结构和实现细节，不是看教科书结论。
- 边数
E （比如网格图、社交网络采样子图）→ 优先 <code>Kruskal；反之如完全图、邻接矩阵存储的图 →Prim更稳 -
networkx的Prim实现底层用的是heapq，但如果你手写并用list.index(min())模拟，那再稠密也比不过排序后的Kruskal - 内存敏感场景：
Kruskal需存所有边排序，Prim只存当前 frontier，边特别多时后者更省内存 - 真正容易被忽略的点：两种算法对「负权边」都完全支持，但如果你的图有负权且还用了
Prim的简化版（没处理松弛更新），就会出错
