如何基于NetworkX最小生成树绘制树状图？

你遇到的问题核心在于误解了linkage函数的输入要求，以及MST邻接矩阵和距离矩阵的区别。让我一步步帮你解决：

为什么你的原有方法行不通？ #

• 你用nx.to_pandas_adjacency(T)得到的是MST的邻接矩阵，其中非边元素为0——但这不是真实的节点间距离，linkage会把这些0当成节点间距离为0，错误地将它们合并成簇。
• 如果你把非边设为inf，linkage无法处理无穷大的距离值，自然会返回无效矩阵。

linkage需要的是完整的两两节点距离矩阵（压缩成一维数组），而不是MST的邻接矩阵。但既然你必须遵循「先MST再树状图」的顺序，我们可以把MST的结构转换成符合linkage格式的矩阵。

解决方案：从MST生成linkage格式矩阵 #

MST的边是按最小权重（原始距离）排序的，这正好对应层次聚类的合并顺序——每次合并距离最近的两个簇。我们只需要模拟这个合并过程，生成linkage要求的矩阵即可。

具体步骤&代码 #

假设你已经有：

• 生成MST时用的原始节点集合（比如distances.index）
• MST图对象T（NetworkX生成的）

import numpy as np
from scipy.cluster.hierarchy import dendrogram
import matplotlib.pyplot as plt

# 1. 从MST中提取所有边，按权重（原始距离）从小到大排序
# 假设你的MST边属性里权重键是'weight'，如果不是请替换成实际键名
edges = sorted(T.edges(data=True), key=lambda x: x[2]['weight'])

# 2. 把节点映射到索引（方便后续处理）
node_to_idx = {node: i for i, node in enumerate(distances.index)}
n_nodes = len(node_to_idx)

# 3. 初始化每个节点为独立簇，跟踪每个簇的成员
clusters = {idx: {idx} for idx in range(n_nodes)}
linkage_matrix = []
next_cluster_id = n_nodes  # 新簇的编号从n_nodes开始递增

# 4. 模拟层次聚类的合并过程
for u, v, edge_data in edges:
    u_idx = node_to_idx[u]
    v_idx = node_to_idx[v]
    
    # 找到u和v所属的簇
    cluster_u = None
    cluster_v = None
    for c_id, members in clusters.items():
        if u_idx in members:
            cluster_u = c_id
        if v_idx in members:
            cluster_v = c_id
        if cluster_u and cluster_v:
            break
    
    # 获取当前合并的距离（即MST边的权重）
    merge_distance = edge_data['weight']
    # 合并后簇的大小
    merged_size = len(clusters[cluster_u]) + len(clusters[cluster_v])
    
    # 向linkage矩阵添加一行：[簇1ID, 簇2ID, 合并距离, 簇大小]
    linkage_matrix.append([cluster_u, cluster_v, merge_distance, merged_size])
    
    # 创建新簇并删除旧簇
    clusters[next_cluster_id] = clusters[cluster_u].union(clusters[cluster_v])
    del clusters[cluster_u]
    del clusters[cluster_v]
    next_cluster_id += 1

# 转成numpy数组（scipy的dendrogram需要数组格式）
linkage_matrix = np.array(linkage_matrix)

# 5. 绘制树状图
plt.figure(figsize=(10,10))
dendrogram(
    linkage_matrix,
    labels=distances.index,
    leaf_rotation=90,
    leaf_font_size=14
)
plt.title('Dendrogram Constructed from MST')
plt.tight_layout()
plt.show()

关键说明 #

• 这个方法严格遵循MST的结构：每次合并MST中连接两个独立连通分量的边，正好对应层次聚类中合并距离最近的两个簇。
• 生成的linkage_matrix完全符合scipy的格式要求，因此能正确绘制出和MST结构一致的树状图。

内容的提问来源于stack exchange，提问作者DrGorilla.eth