networkx求最小生成树最省事，但需确保图连通、边权为数值且字段名正确；不连通时返回MST森林，非空图；Kruskal手写关键在并查集路径压缩与按秩合并；Prim需惰性删除堆中过期节点。
Python里用networkx求最小生成树最省事
绝大多数实际场景下，别自己手写Kruskal或Prim——networkx封装得足够稳，接口直白，还自动处理连通性、权重类型、多重边等边界。
常见错误现象：nx.minimum_spanning_tree(G)返回空图，或报NetworkXError: Graph not connected。这是因为输入图不连通，而MST只对连通图有定义；networkx默认不抛异常，但返回的是原图各连通分量的MST森林（即每个连通块一棵树），容易误以为失败。
- 确保图连通：先跑
nx.is_connected(G)，不连通就按需用nx.connected_components(G)拆开处理 - 边权必须存在且为数值：字段名默认是
'weight'，若用cost或dist，得显式传weight='cost' - 稀疏图（边数远小于节点数²）优先选
algorithm='kruskal'；稠密图可试'prim'，但实测差异常不明显
示例：
import networkx as nx<br>G = nx.Graph()<br>G.add_weighted_edges_from([(0,1,2), (1,2,3), (0,2,4)])<br>T = nx.minimum_spanning_tree(G, algorithm='kruskal')
Kruskal手动实现的关键不是排序，而是并查集路径压缩
手写Kruskal时，90%的性能坑和逻辑错出在并查集（Union-Find）上：没做路径压缩，find退化成O(n)，整体从O(E log E)掉到O(E·n)；没按秩合并，树高失控。
立即学习“Python免费学习笔记（深入）”；
使用场景：需要定制边筛选逻辑（比如只取weight > 0.5的边），或教学/面试现场白板编码。
- 边列表必须预先按
weight升序排，但别用sorted(edges, key=lambda x: x[2])反复调用——先存好 -
find函数里必须递归更新父节点：parent[x] = find(parent[x])，否则压缩失效 - 合并时比较秩（rank）而非单纯赋值，避免树退化；初始化
rank全为0
简短示意：
def find(x):<br> if parent[x] != x:<br> parent[x] = find(parent[x]) # 路径压缩在此<br> return parent[x]
Prim用堆实现时，heapq不能直接删元素，得惰性删除
Python标准库heapq不支持remove或decrease_key，所以经典Prim的“更新邻接点权重”操作不能真改堆里元素，否则堆结构崩坏。必须用惰性删除：每次heappop时检查是否已访问过，跳过无效项。
性能影响明显：堆里可能堆积大量过期条目，最坏情况空间O(E)，但实践中只要图不极端稀疏，影响可控。
- 维护一个
in_mst布尔数组（非集合！索引访问O(1)）标记节点是否已入树 - 每次从堆取
(weight, node)后，先查if in_mst[node]: continue - 不要用
dict或set存当前最小权值——用数组min_weight[node] = weight，更新时直接赋值，堆里只管推新元组
错误写法：heapq.heapreplace(heap, (new_w, node))——这会破坏堆序，因node可能不在堆顶。
边权为负、浮点精度、自环重边这些细节真会影响结果
最小生成树理论上允许负权边（Kruskal/Prim都适用），但networkx默认把负权当异常，除非显式设ignore_nan=False且数据里没NaN；而手写代码若用float('inf')初始化距离，遇到负权可能溢出或逻辑错乱。
真实数据常见坑：
- 浮点权值（如
0.1 + 0.2 != 0.3）导致排序不稳定，sorted()结果不可复现；建议转整型放大（int(w * 100)）或用decimal（小规模图） - 自环（
u == v）和重边（多条u-v边）会被networkx自动忽略或保留最大/最小权那条，取决于multigraph设置；手写时务必先过滤自环 - 无向图边存两次（
u-v,v-u）没问题，但Prim遍历时若没去重，同一节点可能被多次加入堆
最容易被忽略的点：图含孤立节点（度为0）时，MST必须包含它（作为单点树），但很多手写代码初始化时漏掉，导致结果少节点。
