Python-сообщество

  
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
import numpy as np
# пример координат вершин графа
vertices = np.array([
    [0, 0],
    [0, 1],
    [1, 0],
    [1, 1],
    [2, 2]
])
# расстояния между вершинами
distances = np.linalg.norm(vertices[:, np.newaxis] - vertices, axis=2)
# создание разреженной матрицы для поиска минимального остовного дерева
sparse_graph = csr_matrix(distances)
# поиск минимального остовного дерева
mst = minimum_spanning_tree(sparse_graph)
# сумма веса ребер минимального остовного дерева
sum_of_weights = mst.sum()
print(sum_of_weights)