如何用NetworkX自动计算邻居间欧氏距离并生成最小生成树

我帮你重构了代码，实现了自动计算节点间欧氏距离，不用再手动输入边的权重啦，同时保留了最小生成树的构建和可视化功能。下面是优化后的完整方案：

核心改动说明 #

• 替换手动输入的边列表：通过遍历所有节点对，自动计算它们的欧氏距离作为边权重，生成全连接图
• 简化节点位置的添加方式：用字典一次性批量设置节点的pos属性，代码更整洁
• 优化可视化细节：调整节点颜色、边的渲染逻辑，让最小生成树的红色边更突出

完整代码 #

import networkx as nx
import matplotlib.pyplot as plt
import seaborn as sns
import math  # 用于计算欧氏距离

sns.set()

# 1. 创建空图
G = nx.Graph()

# 2. 定义所有节点的位置（用字典批量设置更简洁）
node_positions = {
    0: (8.5, 10.5),
    1: (5, 9),
    2: (11.5, 8.5),
    3: (5, 6.5),
    4: (11.5, 5),
    5: (1.5, 3.5),
    6: (4.5, 2.5),
    7: (7, 4.5),
    8: (9, 3.5),
    9: (12.5, 2.5),
    10: (15.5, 4)
}
# 批量添加节点和位置属性
G.add_nodes_from(node_positions.keys())
nx.set_node_attributes(G, node_positions, 'pos')

# 3. 自动计算所有节点对的欧氏距离，添加带权重的边
nodes = list(G.nodes())
for i in range(len(nodes)):
    for j in range(i + 1, len(nodes)):
        u = nodes[i]
        v = nodes[j]
        # 获取两个节点的坐标
        pos_u = G.nodes[u]['pos']
        pos_v = G.nodes[v]['pos']
        # 计算欧氏距离
        distance = math.dist(pos_u, pos_v)
        # 添加带权重的边（保留两位小数让结果更整洁）
        G.add_edge(u, v, weight=round(distance, 2))

# 4. 构建最小生成树（用kruskal算法，和你原来的选择一致）
T = nx.minimum_spanning_tree(G, algorithm='kruskal')

# 5. 可视化部分
node_pos = nx.get_node_attributes(G, 'pos')
edge_weight = nx.get_edge_attributes(G, 'weight')
red_edges = T.edges()

# 设置节点颜色（所有节点用白色，边框加黑色更清晰）
node_col = ['white'] * len(G.nodes)
# 设置边颜色：生成树的边为红色，其他为黑色
edge_col = ['red' if edge in red_edges else 'black' for edge in G.edges()]

# 绘制节点（加node_color参数设置填充色，edgecolors设置边框色）
nx.draw_networkx(G, node_pos, node_color=node_col, node_size=450, edgecolors='black')
# 绘制节点标签
nx.draw_networkx_labels(G, node_pos)
# 绘制边（生成树的边可以设置更粗的线宽，更显眼）
nx.draw_networkx_edges(G, node_pos, edge_color=edge_col, width=[2 if edge in red_edges else 1 for edge in G.edges()])
# 绘制边权重标签
nx.draw_networkx_edge_labels(G, node_pos, edge_labels=edge_weight, font_size=8)

# 关闭坐标轴
plt.axis('off')
# 显示图像
plt.show()

代码解释 #

• 欧氏距离计算：用math.dist()直接计算两个坐标元组的欧氏距离，比手动计算平方根更简洁可靠
• 全连接图生成：遍历所有i<j的节点对，避免重复添加边（比如(0,1)和(1,0)是同一条边）
• 可视化优化：给生成树的边设置更粗的线宽，让结果更直观；节点添加黑色边框，避免白色节点和背景融合

这样你就完全不用手动计算邻居距离啦，不管节点数量怎么变，代码都能自动生成对应的边权重和最小生成树。

内容的提问来源于stack exchange，提问作者Elvissmog