SciPy 的 minimum_spanning_tree 会忽略权重为零的边（视作缺失），导致本应存在的零权 MST 边丢失；本文介绍一种安全、等价的偏移法——对所有边权加 1 再减 1，从而在保持 MST 结构不变的前提下完整保留零权边信息。
scipy 的 `minimum_spanning_tree` 会忽略权重为零的边（视作缺失），导致本应存在的零权 mst 边丢失；本文介绍一种安全、等价的偏移法——对所有边权加 1 再减 1，从而在保持 mst 结构不变的前提下完整保留零权边信息。
在使用 SciPy 计算最小生成树（MST）时，一个常见但易被忽视的问题是：稀疏矩阵中权重为 0 的边会被 minimum_spanning_tree 视为“不存在”而非“零代价边”。这是因为 SciPy 内部基于 scipy.sparse 矩阵（如 CSR/CSC）实现，其 .data 属性仅存储非零元素，而显式的 0 值在构造稀疏矩阵时默认被丢弃（即使你手动赋值 X[0,2] = 0，只要该位置原无数据，X.data 中也不会新增条目）。
因此，尽管图中存在合法的零权边（如 (0,2)），且该边在理论 MST 中可能被选中（例如当它连接两个连通分量且无更小正权边可选时），minimum_spanning_tree 的输出却只包含非零权重边，导致结构信息丢失。
✅ 解决方案：权重偏移法（Offset Trick）
核心思想是——对所有边权统一加一个常数（如 +1），计算 MST 后再统一减回。该操作不改变 MST 的拓扑结构，理由如下：
- 所有生成树均含恰好 n−1 条边；
- 给每条边加 δ，则任意生成树总权重增加 (n−1)·δ；
- 因此各生成树之间的权重差保持不变 → 最小性关系完全保留。
⚠️ 前提：图中无负权边（否则加常数可能改变相对序关系；若存在负权，可先平移至全非负再应用）。
以下是完整可运行示例：
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
# 构建原始图（注意：显式零需确保进入 .data）
X = csr_matrix([
[0, 3, 0, 2],
[3, 0, 3, 5],
[0, 3, 0, 2],
[2, 5, 2, 0]
])
# 强制将 (0,2) 和 (2,0) 设为 0 并纳入稀疏结构（关键！）
X = X.tolil()
X[0, 2] = 0
X[2, 0] = 0
X = X.tocsr()
# ✅ 偏移法：所有非零边权 +1（注意：稀疏矩阵中 0 不在 .data，故只需处理 .data）
X_shifted = X.copy()
X_shifted.data += 1 # 仅作用于实际存储的非零项
T_shifted = minimum_spanning_tree(X_shifted)
T_original_weights = T_shifted.copy()
T_original_weights.data -= 1 # 还原权重
print("Recovered MST with zero-weight edges:")
print(T_original_weights.toarray())
print(f"Non-zero entries (including zeros!): {T_original_weights.nnz}")
输出将正确包含 (0,2) 边（权重 0.0），且 nnz 计数反映真实边数（含零权）。
? 重要注意事项：
- X.data += 1 仅修改已存在的非零项；若某零权边原本未被存储（即 .data 中无对应位置），该方法仍无法恢复它——因此务必确保零权边在输入矩阵中以显式方式存在于 .data 中（推荐用 LIL 格式赋值后转 CSR）；
- 此法适用于所有非负权图；若含负权，先计算 min_weight = X.data.min()，令 offset = -min_weight + 1，再执行 X.data += offset，最后还原；
- 输出 T_original_weights 是标准 CSR 矩阵，零权边以 0.0 显式存在，可通过 find() 或布尔索引提取全部边。
通过这一简洁而严谨的偏移策略，你既能复用 SciPy 高效的 MST 实现，又能完整保留在算法语义上至关重要的零权边信息。
