В связном взвешенном неориентированном графе остовное дерево — это набор рёбер, который соединяет все вершины и не содержит циклов. Остовное дерево наименьшего веса называется минимальным остовным деревом (MST). Классический пример: соединить офисы наименьшим количеством кабеля.

Взвешенный граф и MST (зелёные рёбра, вес 39)
Взвешенный граф и MST (зелёные рёбра, вес 39)

Свойства

  • В MST ровно V - 1 ребро: меньше — нарушается связность, больше — появляется цикл.
  • Свойство разреза: если разбить вершины на две части, самое лёгкое ребро между ними входит в некоторое MST. На этом держится корректность жадных алгоритмов.
  • Если веса различны, MST единственно.

Алгоритм Краскала

Сортируем рёбра по возрастанию веса. Берём ребро, если его концы в разных компонентах; иначе возник бы цикл. Компоненты отслеживаем через Union-Find. Когда набрано V - 1 рёбер, можно остановиться.

python
NODES = "ABCDEFG"
EDGES = [(7, "A", "B"), (5, "A", "D"), (8, "B", "C"), (9, "B", "D"), (7, "B", "E"),
         (5, "C", "E"), (15, "D", "E"), (6, "D", "F"), (8, "E", "F"), (9, "E", "G"),
         (11, "F", "G")]          # (weight, u, v): cable lengths between offices

def kruskal(nodes, edges):
    parent = {v: v for v in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x