DEV//UNIT
← АлгоритмыGraphs

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

MST: рёбра по возрастанию веса, создающие цикл — отбрасываем.

время O(E log E)память O(E)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function kruskal(edges: Edge[]): Edge[] {
2  const sorted = [...edges].sort((a, b) => a.weight - b.weight)
3  const uf = new UnionFind()
4  const mst: Edge[] = []
5 
6  for (const e of sorted) {
7    if (uf.find(e.from) !== uf.find(e.to)) {
8      uf.union(e.from, e.to)
9      mst.push(e)
10    }
11  }
12 
13  return mst
14}

Проблема

MST: рёбра по возрастанию веса, создающие цикл — отбрасываем.

Что вы видите

Рёбра сортируются; Union-Find проверяет, не замкнёт ли ребро цикл.

Как это работает

Жадность работает: минимальное остовное дерево собирается из локально лучших рёбер. Сортировка + DSU = O(E log E).

Пошаговый разбор

  1. 01

    Сортировка

    Рёбра по весу.

  2. 02

    Проверка

    Union-Find: один корень — цикл.

  3. 03

    Набор

    V−1 ребро — дерево готово.

Complexity и ограничения

time
O(E log E)
space
O(E)

См. complexity в шапке страницы.

Edge cases

  • Пустой вход

    Корректно завершается без лишних шагов.

  • Вырожденный случай

    Минимум работы — сразу ответ.

Где встречается в реальности

Продукт

Классический приём в реальных системах.

Собеседования

Стандартный вопрос на понимание структуры.

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

Union-Find (DSU)Алгоритм Прима
Shorts

«Соединить всё подешевле: Краскал»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Соединить всё подешевле: Краскал
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/kruskal