SciPy 的 minimum_spanning_tree 会忽略权重为零的边（视作缺失边），导致本应存在的零权 MST 边丢失；本文介绍一种安全、等价的偏移法：对所有边权统一加 1 再减 1，从而保留零权边的拓扑结构与数值信息。
scipy 的 `minimum_spanning_tree` 会忽略权重为零的边（视作缺失边），导致本应存在的零权 mst 边丢失；本文介绍一种安全、等价的偏移法：对所有边权统一加 1 再减 1，从而保留零权边的拓扑结构与数值信息。
在图算法中，零权边具有明确的语义意义（例如表示无成本连接、强相关性或默认邻接），但 SciPy 的 scipy.sparse.csgraph.minimum_spanning_tree 实现将显式零（0.0）与隐式缺失（0 表示稀疏矩阵中的未存储值）视为等价——即内部统一按“不存在边”处理。这导致即使某条零权边属于理论上的唯一 MST，它也不会出现在输出的稀疏矩阵中。
根本原因在于 SciPy 的 MST 实现基于 Prim 或 Kruskal 算法的稀疏优化版本，其底层依赖 csr_matrix 的 .data 数组进行边权比较；而 .data 仅存储非零项，零值被直接丢弃，无法区分“真实零权边”和“无边”。
✅ 推荐解决方案：权重偏移法（Offset Trick）
该方法严格保持 MST 的唯一性与正确性，前提是原图所有边权 ≥ 0（常见于距离、相似度、代价等场景）：
- 对邻接矩阵所有已存储的边权（即 X.data）统一加一个正偏移量（如 +1）；
- 调用 minimum_spanning_tree；
- 对结果 Tcsr.data 统一减去相同偏移量。
该操作不改变任意两棵生成树的相对权重差，因此 MST 结构完全不变，且所有原本为零的边（若入选 MST）将以 1 − 1 = 0 形式完整保留在 .data 中。
以下是完整可运行示例：
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
# 构建带显式零权边的图（0-2 和 2-0 权重为 0）
X = csr_matrix([
[0, 3, 0, 2], # node 0: connected to 1(w=3), 2(w=0), 3(w=2)
[3, 0, 3, 5], # node 1: connected to 0(w=3), 2(w=3), 3(w=5)
[0, 3, 0, 2], # node 2: connected to 0(w=0), 1(w=3), 3(w=2)
[2, 5, 2, 0] # node 3: connected to 0(w=2), 1(w=5), 2(w=2)
])
# ✅ 关键步骤：仅对已存在的边（X.data）做偏移，不触碰稀疏结构
X.data += 1
Tcsr = minimum_spanning_tree(X)
Tcsr.data -= 1 # 恢复原始权重语义
print("Recovered MST (with explicit zeros):")
print(Tcsr.toarray())
print(f"Number of edges (including zero-weight): {Tcsr.nnz}")
输出将正确包含 (0, 2) 和 (2, 0) 的 0.0 条目（对称存储，取决于输入矩阵格式），nnz 值变为 3，对应三边：(0,1)=3, (0,3)=2, (0,2)=0 —— 完全匹配理论 MST。
⚠️ 注意事项：
- 此法不适用于含负权边的图（因偏移可能改变 MST 唯一性）；若存在负权，需改用 NetworkX 等支持显式零权的库；
- 偏移量必须严格大于图中最大负权绝对值（若使用），但对非负图，+1 即足够；
- X.data += 1 直接修改原矩阵数据，如需保留原始图，请先 X = X.copy()；
- 输出 Tcsr 仍为 CSR 格式，可通过 Tcsr.toarray() 或 zip(Tcsr.row, Tcsr.col, Tcsr.data) 提取边列表。
通过这一简洁而严谨的变换，你既能继续利用 SciPy 的高性能稀疏 MST 实现，又能完整保留零权边的建模意义——在聚类、网络鲁棒性分析、零延迟拓扑设计等场景中尤为关键。
