1	2	3	4	5	6	7	8	9	10	11	12	13	14
1		23			54		55				26			
2	23		56		18									
3		56		50	44	61								
4			50			28				27				
5	54	18	44			51	34	56	48					
6			61	28	51				27	42				
7	55				34			36				38		
8					56		36		29			33		
9					48	27		29		61		29	42	36
10				27		42			61					25
11	26											24		
12							38	33	29		24		30	
13									42			30		47
14									36	25			47	

import numpy as np
import pandas as pd
from scipy.sparse import coo_matrix
import networkx as nx
import matplotlib.pyplot as plt

"""
numpy: 1.24.3
pandas: 1.5.3
networkx: 3.1
matplotlib: 3.7.5
"""

# 避免图片无法显示中文
plt.rcParams['font.sans-serif'] = ['SimHei']
# 显示所有列
pd.set_option('display.max_columns', None)
pd.set_option('display.width', 1000)

# 读取数据
data = pd.read_excel(io='data.xlsx', sheet_name='Sheet1', index_col=0)
data = data.fillna(0)
print('矩阵的空值以0填充：\n', data)
coo = coo_matrix(np.array(data))
# 矩阵行列的索引默认从0开始改成从1开始
coo.row += 1
coo.col += 1
data = [int(i) for i in coo.data]
coo_tuple = list(zip(coo.row, coo.col, data))
coo_list = []
for i in coo_tuple:
    coo_list.append(list(i))

# 出发点
start_node = 1
# 目的地
target_node = 14
# 设置各顶点坐标（只是方便绘图，并不是实际位置）
pos = {1: (1, 8), 2: (4, 10), 3: (11, 11), 4: (14, 8), 5: (5, 7), 6: (10, 6), 7: (3, 5), 8: (6, 4), 9: (8, 4),
       10: (14, 5), 11: (2, 3), 12: (5, 1), 13: (8, 1), 14: (13, 3)}

# 创建空的无向图
G = nx.Graph()
# 给无向图的边赋予权值
G.add_weighted_edges_from(coo_list)

# 最小生成树的求解：kruskal克鲁斯卡尔算法，prim普里姆算法，boruvka博鲁夫卡算法
plt.figure()
plt.suptitle('kruskal/prim/boruvka算法：最小生成树')
T = nx.minimum_spanning_tree(G, algorithm='kruskal')
# T=nx.minimum_spanning_tree(G, algorithm='prim')
# T=nx.minimum_spanning_tree(G, algorithm='boruvka')
# 绘制无向加权图
nx.draw(G, pos, with_labels=True)
# 设置最小生成树的顶点颜色
nx.draw_networkx_nodes(G, pos, nodelist=T.nodes, node_color='yellow', edgecolors='red')
# 设置最小生成树的边颜色和宽度
nx.draw_networkx_edges(G, pos, edgelist=T.edges, edge_color='blue', width=5)
# 显示无向加权图的边的权值
labels = nx.get_edge_attributes(G, name='weight')
# 显示边的权值
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_color='purple', font_size=10)
nx.draw_networkx_nodes(G, pos, nodelist=[start_node], node_color='#00ff00', edgecolors='red')
plt.show()