Минимальное остовное дерево

Минимальное остовное дерево (Minimum Spanning Tree, MST) — подграф взвешенного связного неориентированного графа, соединяющий все вершины без циклов с минимально возможной суммой весов рёбер.

Зачем нужно

MST решает задачу «как соединить n узлов с минимальными затратами». Это одна из классических задач оптимизации графов, применяемая в сетевом проектировании, кластеризации и приближённых решениях для NP-трудных задач. Алгоритмы Крускала и Прима решают её за O(E log E).

Где используется

  • Сетевое проектирование: прокладка кабелей с минимальной длиной
  • Кластеризация данных (single-linkage clustering)
  • Приближённые алгоритмы для TSP (задача коммивояжёра)
  • Электрические схемы: минимальная разводка
  • Компьютерные сети: spanning tree protocol (STP)

Основной контент

Алгоритм Крускала (Kruskal's algorithm)

Жадный подход: сортируем рёбра по весу, добавляем ребро если оно не создаёт цикл.

// Union-Find для обнаружения циклов
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false; // цикл!
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

function kruskal(n, edges) {
  // edges: [{u, v, weight}]
  edges.sort((a, b) => a.weight - b.weight);
  const uf = new UnionFind(n);
  const mst = ;
  let totalWeight = 0;

  for (const { u, v, weight } of edges) {
    if (uf.union(u, v)) { // нет цикла — добавляем ребро
      mst.push({ u, v, weight });
      totalWeight += weight;
      if (mst.length === n - 1) break; // MST готов
    }
  }
  return { mst, totalWeight };
}

// Пример: 4 вершины, 5 рёбер
const edges = [
  { u: 0, v: 1, weight: 10 },
  { u: 0, v: 2, weight: 6  },
  { u: 0, v: 3, weight: 5  },
  { u: 1, v: 3, weight: 15 },
  { u: 2, v: 3, weight: 4  },
];
const { mst, totalWeight } = kruskal(4, edges);
// mst: [2-3(4), 0-3(5), 0-1(10)], totalWeight = 19

Алгоритм Прима (Prim's algorithm)

Начинает от одной вершины и жадно расширяет дерево, добавляя минимальное ребро к следующей вершине.

function prim(graph, start = 0) {
  // graph: массив массивов [{to, weight}]
  const n = graph.length;
  const inMST = new Array(n).fill(false);
  const key = new Array(n).fill(Infinity);    // минимальный вес ребра до вершины
  const parent = new Array(n).fill(-1);
  key[start] = 0;
  let totalWeight = 0;

  for (let count = 0; count < n; count++) {
    // Выбираем вершину с минимальным key (в CP используют min-heap)
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!inMST[v] && (u === -1 || key[v] < key[u])) u = v;
    }
    inMST[u] = true;
    totalWeight += key[u];

    for (const { to, weight } of graph[u]) {
      if (!inMST[to] && weight < key[to]) {
        key[to] = weight;
        parent[to] = u;
      }
    }
  }
  return { parent, totalWeight };
}

Сравнение алгоритмов

Алгоритм Время Лучше для
Kruskal O(E log E) Разреженные графы
Prim (массив) O(V^2) Плотные графы
Prim (min-heap) O(E log V) Разреженные графы

Свойства MST

  • MST не единственно при равных весах рёбер
  • Для n вершин MST содержит ровно n-1 рёбер
  • MST не обязательно содержит кратчайшие пути между вершинами

Частые ошибки

  • Путать MST с кратчайшим путём: MST минимизирует сумму рёбер дерева, а не пути между парами вершин.
  • Применять алгоритмы к ориентированному графу — нужен алгоритм Эдмондса для directed MST.
  • Не использовать Union-Find в Крускале — наивная проверка цикла через DFS даёт O(V) на ребро.
  • Применять к несвязному графу — MST не существует; можно построить MSF (minimum spanning forest).

Связанные темы

Ресурсы