Минимальное остовное дерева графа по алгоритму Краскала

using DataFrames, Plots

using Graphs, SimpleWeightedGraphs

using XLSX

]status

# Pkg.add(["XLSX", "Graphs", "SimpleWeightedGraphs"])

# Считывает данные с Excel-файла три столбца, оборачиваем в таблицу с шапочкой для наглядности.
dano = DataFrame(XLSX.readdata("ZhD_rebra.xlsx", "жд_ВсеПроекты_км", "I2:Q48"), ["УзелН", "УзелК", "УзелНачала", "УзелКонец", "Расстояние", "X1_i", "Y1_i", "X2_i", "Y2_i"]) 

# Число ребер (дуг) r = количеству строк в таблице
r = nrow(dano)
# Число узлов (вершин)
n = max(maximum(dano[:,:УзелНачала]), maximum(dano[:,:УзелКонец])) 
println( "Количество вершин = ", n)
println("Количество ребер = ", r )

# Строим граф
GraphZhd=SimpleWeightedGraph(n)  # используйте "Простой взвешенный Орграф" для неориентированных графов

 #добавляем ребра с их расстояниями (весами) из таблицы "dano"
for i=1:r
    add_edge!(GraphZhd, dano[i,:УзелНачала], dano[i,:УзелКонец], dano[i,:Расстояние])
end
# Если вместо расстояния поставить 1, то получим невзвешанный, неориентированный  граф
GraphZhd

#  проверяем кол-во вершин и ребер графа на построенном нами графе
vershiny = nv(GraphZhd) # Количество вершин 
rebra = ne(GraphZhd)   # Количество ребер 
println( "Количество вершин = ", vershiny)
println("Количество ребер = ", rebra )

#= Возвращает вектор ребер, представляющий минимальное (по умолчанию) остовное дерево связного неориентированного графа GraphZhd
с матрицей расстояний, используя алгоритм Крускала .=#
mintree = kruskal_mst(GraphZhd; minimize=true)

# Справочная информация для вывода показателей из вектора, вычисленного по алгоритму Краскала.
mintree[1].src  # номер вершины начала_ребра 1
mintree[1].dst  # номер вершины конец_ребра 1
mintree[1].weight # вес ребра 1

vershiny_1 = Int64[mintree[i].src for i in 1:length(mintree)] # номера вершин начало ребер минимального остова
vershiny_2 = Int64[mintree[i].dst for i in 1:length(mintree)]  # номера вершин конца ребер минимального остова
dist = Float64[mintree[i].weight for i=1:length(mintree)]# вес ребра

# Количество ребер в минимальном остове стало
length(mintree)

# Число вершин в минимальном остове должны остаться все
n_min = max(maximum(vershiny_1), maximum(vershiny_2) )

# Таблица по результатам вычисления (узлы и ребра минимального остова графа)

min_result = DataFrame([vershiny_1 vershiny_2], ["УзелСтарт", "УзелФиниш"]) 

# считывает исходные данные вершин графа

дано = DataFrame(XLSX.readdata("ZhD_rebra.xlsx", "жд_ВсеПроекты_км", "B2:F43"), ["НазваниеУзла", "НомерНаКарте", "Номер_пп", "X", "Y"]) 

# Создаём словарь: Номер_пп → X-координата
dict_X = Dict(дано.Номер_пп .=> дано.X)

# Добавляем столбец с X-координатой, подставляя 0 при отсутствии
#Это в точности имитирует работу ВПР: поиск значения в первом столбце диапазона и возврат значения из заданного столбца.
min_result.X1 = [get(dict_X, Номер_пп, 0) for Номер_пп in min_result.УзелСтарт]
min_result.X2 = [get(dict_X, Номер_пп, 0) for Номер_пп in min_result.УзелФиниш]


# Создаём словарь: Номер_пп → Y-координата
dict_Y = Dict(дано.Номер_пп .=> дано.Y)

# Добавляем столбец с X-координатой, подставляя 0 при отсутствии
#Это в точности имитирует работу ВПР: поиск значения в первом столбце диапазона и возврат значения из заданного столбца.
min_result.Y1 = [get(dict_Y, Номер_пп, 0) for Номер_пп in min_result.УзелСтарт]
min_result.Y2 = [get(dict_Y, Номер_пп, 0) for Номер_пп in min_result.УзелФиниш]

# Выводим таблицу, дополненную координатами узлов
min_result

# Стоим ребра опорной железнодорожной сети ЕиПСР

p = plot(size=(1000, 800), legend=false) # отключение легенды (опционально)
for row in eachrow(dano)
        plot!([row.X1_i, row.X2_i], [row.Y1_i, row.Y2_i],
             color=:black, # чёрный цвет
             linewidth=3,   # толщина (опционально)
             linestyle = :dash,  # штриховая линия
             label="",  
             xaxis = false,   # убрать ось X
             yaxis = false,   # убрать ось Y
     background_color = :transparent)      # прозрачный фон графика
end
p

 # Стоим ребра железнодорожной сети ЕиПСР минимального остова (по алгоритму Краскаля), розовый прозрачный
for row in eachrow(min_result)
        plot!([row.X1, row.X2], [row.Y1, row.Y2], 
              color=:red, alpha=0.4, linewidth=9, label="")  # alpha=прозрачность 0.4
    end
p

 # Собираем все узлы 
    all_nodes = vcat(dano.УзелНачала, dano.УзелКонец)
    all_x = vcat(dano.X1_i, dano.X2_i)
    all_y = vcat(dano.Y1_i, dano.Y2_i)

# Уникальные узлы с их координатами
    unique_nodes = Dict{Int, Tuple{Float64, Float64}}()
    for (node, x, y) in zip(all_nodes, all_x, all_y)
        if !haskey(unique_nodes, node)
            unique_nodes[node] = (x, y)
        end
    end

 # Рисуем узлы сети, которые являются ж/д станциями
    for (node, (x, y)) in unique_nodes
        scatter!([x], [y], 
                 markersize=15,
                 color=:white,
                 markerstrokewidth=2,
                 markerstrokecolor=:grey, 
                 label="")
                     
        annotate!(x, y, text("$node", 10, :black, :center))
    end
# Можно добавить заголовок и сохранить рисунок (в данном примере фон прозрачный)
title!("Минимальный остов сети, расчитанный по алгоритму Краскала", titlefontsize = 10)
savefig(p, "жд_ВсеПроекты.png")
p