Какой алгоритм поддерживается в Golang для вычисления минимального остовного дерева?

@carmelo_larson 

В языке программирования Golang существует пакет gonum, который предоставляет реализацию алгоритма Крускала для вычисления минимального остовного дерева на неориентированных графах.

Алгоритм Крускала состоит из следующих шагов:

1. Создать пустой граф минимального остовного дерева.
2. Отсортировать все ребра в порядке возрастания их весов.
3. Перебирать отсортированные ребра по порядку и добавлять их в граф минимального остовного дерева, если они не образуют цикл с уже добавленными ребрами.

Пример использования пакета gonum для вычисления минимального остовного дерева:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

package main

import (
    "fmt"

    "gonum.org/v1/gonum/graph"
    "gonum.org/v1/gonum/graph/simple"
    "gonum.org/v1/gonum/graph/algorithm"
)

func main() {
    g := simple.NewUndirectedGraph()
    n1 := g.NewNode()
    n2 := g.NewNode()
    n3 := g.NewNode()
    g.AddNode(n1)
    g.AddNode(n2)
    g.AddNode(n3)
    g.SetEdge(simple.Edge{F: n1, T: n2, W: 1.0})
    g.SetEdge(simple.Edge{F: n2, T: n3, W: 2.0})
    g.SetEdge(simple.Edge{F: n3, T: n1, W: 3.0})

    mst := algorithm.Kruskal(g)

    for _, e := range mst.Edges() {
        fmt.Printf("(%d)-[%0.2f]->(%d)
", e.From().ID(), e.Weight(), e.To().ID())
    }
}

В этом примере мы создаем неориентированный граф с тремя вершинами и тремя ребрами. Затем мы вызываем функцию algorithm.Kruskal() для вычисления минимального остовного дерева графа. Результатом будет новый граф, содержащий только ребра, которые входят в минимальное остовное дерево. Мы выводим каждое ребро с его весом в консоль.