Взвешенные графы: минимальный остов и кратчайший путь

Взвешенные графы простыми словами: минимальное остовное дерево, алгоритм Дейкстры, труднорешаемые задачи — и почему Дейкстру на приоритетной очереди пишут с оговорками.

Опубликовано 19 июля 2026 обновлено 15 октября 2026 ~21 мин чтения

← назад к разделу

В обычном графе ребро либо есть, либо нет. Но в жизни у связей есть цена: дорога длиннее или короче, кабель дороже или дешевле. Когда рёбрам приписывают числа-веса, граф становится взвешенным, и появляются две классические задачи: соединить всё дёшево и добраться быстро.

Обязательно

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

Задача: есть города, между некоторыми можно проложить кабель, у каждой линии своя стоимость. Нужно соединить все города так, чтобы суммарная стоимость была минимальной. Ответ — минимальное остовное дерево (MST, minimum spanning tree): набор рёбер, связывающий все вершины без циклов и с наименьшей суммой весов.

Строят его жадно — этот способ называют алгоритмом Прима. Начинают с одной вершины и на каждом шаге добавляют самое дешёвое ребро, ведущее из уже подключённой части к ещё не подключённой вершине, — пока не подключат все. Чтобы быстро находить самое дешёвое ребро, используют приоритетную очередь. Так проектируют сети: кабельные, дорожные, электрические.

Почему жадный выбор здесь не врёт, хотя обычно жадность обманывает. Разрежьте вершины на две части: подключённые и остальные. Любой остов обязан содержать хотя бы одно ребро через этот разрез, иначе части не связаны. Если самое дешёвое ребро через разрез в остов не вошло, добавьте его: получится цикл, в котором есть и другое ребро через разрез, не дешевле; уберите то другое, и остов стал не дороже. Значит, самое дешёвое ребро через любой разрез входит в какой-то минимальный остов, и Прим на каждом шаге берёт ровно такое. Это свойство разреза, и оно же оправдывает Краскала ниже; где жадность работает, а где нет, разбирает статья про динамическое программирование.

живой пример

import java.util.*;

public class Prim {
    public static void main(String[] args) {
        int[][][] adj = {
                {{1, 2}, {2, 5}}, {{0, 2}, {2, 1}, {3, 4}}, {{0, 5}, {1, 1}, {3, 3}}, {{1, 4}, {2, 3}}};
        boolean[] inTree = new boolean[adj.length];
        PriorityQueue<int[]> edges = new PriorityQueue<>(Comparator.comparingInt(e -> e[2]));
        inTree[0] = true;
        for (int[] e : adj[0]) edges.add(new int[]{0, e[0], e[1]});
        int total = 0;
        while (!edges.isEmpty()) {
            int[] e = edges.poll();
            if (inTree[e[1]]) continue;
            inTree[e[1]] = true;
            total += e[2];
            System.out.println("взяли ребро " + e[0] + "–" + e[1] + " весом " + e[2]);
            for (int[] next : adj[e[1]]) if (!inTree[next[0]]) edges.add(new int[]{e[1], next[0], next[1]});
        }
        System.out.println("стоимость остова: " + total);
    }
}

Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

package main

import (
	"container/heap"
	"fmt"
)

type edgeHeap [][3]int // {откуда, куда, вес}

func (h edgeHeap) Len() int           { return len(h) }
func (h edgeHeap) Less(i, j int) bool { return h[i][2] < h[j][2] }
func (h edgeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *edgeHeap) Push(x any)        { *h = append(*h, x.([3]int)) }
func (h *edgeHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func main() {
	adj := [][][2]int{
		{{1, 2}, {2, 5}}, {{0, 2}, {2, 1}, {3, 4}}, {{0, 5}, {1, 1}, {3, 3}}, {{1, 4}, {2, 3}},
	}
	inTree := make([]bool, len(adj))
	edges := &edgeHeap{}
	inTree[0] = true
	for _, e := range adj[0] {
		heap.Push(edges, [3]int{0, e[0], e[1]})
	}
	total := 0
	for edges.Len() > 0 {
		e := heap.Pop(edges).([3]int)
		if inTree[e[1]] {
			continue
		}
		inTree[e[1]] = true
		total += e[2]
		fmt.Printf("взяли ребро %d–%d весом %d\n", e[0], e[1], e[2])
		for _, next := range adj[e[1]] {
			if !inTree[next[0]] {
				heap.Push(edges, [3]int{e[1], next[0], next[1]})
			}
		}
	}
	fmt.Println("стоимость остова:", total)
}

Запустить

живой пример

class MinHeap {
  constructor(less) {
    this.a = [];
    this.less = less;
  }
  get size() { return this.a.length; }
  push(v) {
    const a = this.a;
    let i = a.push(v) - 1;
    while (i > 0 && this.less(a[i], a[(i - 1) >> 1])) {
      const p = (i - 1) >> 1;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (2 * i + 1 < a.length) {
        let c = 2 * i + 1;
        if (c + 1 < a.length && this.less(a[c + 1], a[c])) c++;
        if (!this.less(a[c], a[i])) break;
        [a[i], a[c]] = [a[c], a[i]];
        i = c;
      }
    }
    return top;
  }
}

const adj = [
  [[1, 2], [2, 5]], [[0, 2], [2, 1], [3, 4]], [[0, 5], [1, 1], [3, 3]], [[1, 4], [2, 3]],
];
const inTree = new Array(adj.length).fill(false);
const edges = new MinHeap((x, y) => x[2] < y[2]);
inTree[0] = true;
for (const [to, w] of adj[0]) edges.push([0, to, w]);
let total = 0;
while (edges.size > 0) {
  const [from, to, w] = edges.pop();
  if (inTree[to]) continue;
  inTree[to] = true;
  total += w;
  console.log(`взяли ребро ${from}–${to} весом ${w}`);
  for (const [next, nw] of adj[to]) if (!inTree[next]) edges.push([to, next, nw]);
}
console.log("стоимость остова:", total);

Запустить

живой пример

import heapq

adj = [[(1, 2), (2, 5)], [(0, 2), (2, 1), (3, 4)], [(0, 5), (1, 1), (3, 3)], [(1, 4), (2, 3)]]
in_tree = [False] * len(adj)
edges: list[tuple[int, int, int]] = []     # (вес, откуда, куда): куча сравнивает по весу
in_tree[0] = True
for to, w in adj[0]:
    heapq.heappush(edges, (w, 0, to))
total = 0
while edges:
    w, frm, to = heapq.heappop(edges)
    if in_tree[to]:
        continue
    in_tree[to] = True
    total += w
    print(f"взяли ребро {frm}–{to} весом {w}")
    for nxt, nw in adj[to]:
        if not in_tree[nxt]:
            heapq.heappush(edges, (nw, to, nxt))
print("стоимость остова:", total)

Запустить

Каждое ребро попадает в очередь не больше двух раз и достаётся за O(log E), итого O(E·log V): та же оценка, что у Дейкстры, и тот же приём с пропуском устаревших записей, о котором ниже.

Прим растит остов шаг за шагом: очередь всегда отдаёт самое дешёвое ребро наружу, а рёбра к уже подключённым вершинам пропускаются.

Кратчайший путь: алгоритм Дейкстры

Другая задача — не «связать всё», а «добраться из A в B быстрее всего»: найти кратчайший маршрут по дорогам с известной длиной. Классическое решение — алгоритм Дейкстры.

Для каждой вершины держим текущую лучшую известную дистанцию от старта; вначале у старта она 0, у остальных — «бесконечность». На каждом шаге берут ближайшую ещё не обработанную вершину и «расслабляют» её соседей: если через неё до соседа получается короче, чем было известно, — обновляют дистанцию соседа. Обработанную вершину больше не трогают: её дистанция уже окончательна. Повторяют, пока не обработают все.

Аналогия — как вода от источника: до ближайших точек она доходит первой, и до каждой — по кратчайшему пути. Чтобы каждый раз быстро брать «ближайшую необработанную вершину», Дейкстра опирается на приоритетную очередь — ту же кучу. Отсюда навигаторы и маршрутизация в сетях.

Важная оговорка: классический Дейкстра требует, чтобы веса рёбер были неотрицательными. Причина в самой его механике: вершину, до которой найдено расстояние, он объявляет обработанной и больше к ней не возвращается. Это законно, только пока любой дальнейший шаг может путь лишь удлинить. Появись ребро с отрицательным весом — и уже закрытую вершину задним числом можно было бы удешевить, а Дейкстра этого не заметит и выдаст неверный ответ. Когда отрицательные веса всё-таки есть (например, это не расстояния, а прибыль и убыток), берут алгоритм Беллмана — Форда: он медленнее, зато пересматривает оценки много раз и попутно ловит отрицательные циклы, в которых кратчайшего пути нет вовсе.

Дейкстра выбирает путь по наименьшей сумме весов: S→A→C→T стоит 2+2+3=7, а путь через B — 5+4=9. Считается сумма весов, а не число рёбер.

Тот же граф в коде. Программа печатает, в каком порядке Дейкстра забирает вершины из очереди: строго по возрастанию дистанции — и B попадает в обработку, хотя на кратчайшем пути её нет.

живой пример

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        String[] name = {"S", "A", "B", "C", "T"};
        int[][] edges = {{0, 1, 2}, {0, 2, 5}, {1, 3, 2}, {3, 4, 3}, {2, 4, 4}};
        int[][] w = new int[name.length][name.length];
        for (int[] e : edges) { w[e[0]][e[1]] = e[2]; w[e[1]][e[0]] = e[2]; }
        int[] dist = new int[name.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        Queue<int[]> frontier = new PriorityQueue<>(Comparator.comparingInt(pair -> pair[1]));
        frontier.add(new int[]{0, 0});
        System.out.print("порядок обработки: ");
        while (!frontier.isEmpty()) {
            int[] cur = frontier.poll();
            if (cur[1] > dist[cur[0]]) continue;
            System.out.print(name[cur[0]] + "(" + cur[1] + ") ");
            for (int v = 0; v < name.length; v++) {
                if (w[cur[0]][v] == 0) continue;
                int viaCur = cur[1] + w[cur[0]][v];
                if (viaCur < dist[v]) {
                    dist[v] = viaCur;
                    frontier.add(new int[]{v, viaCur});
                }
            }
        }
        System.out.println("\nдо T добрались за " + dist[4]);
    }
}

Запустить

живой пример

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type pairHeap [][2]int // {вершина, дистанция}

func (h pairHeap) Len() int           { return len(h) }
func (h pairHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h pairHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *pairHeap) Push(x any)        { *h = append(*h, x.([2]int)) }
func (h *pairHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func main() {
	name := []string{"S", "A", "B", "C", "T"}
	edges := [][3]int{{0, 1, 2}, {0, 2, 5}, {1, 3, 2}, {3, 4, 3}, {2, 4, 4}}
	n := len(name)
	w := make([][]int, n)
	for i := range w {
		w[i] = make([]int, n)
	}
	for _, e := range edges {
		w[e[0]][e[1]], w[e[1]][e[0]] = e[2], e[2]
	}
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[0] = 0
	frontier := &pairHeap{{0, 0}}
	fmt.Print("порядок обработки: ")
	for frontier.Len() > 0 {
		cur := heap.Pop(frontier).([2]int)
		if cur[1] > dist[cur[0]] {
			continue
		}
		fmt.Printf("%s(%d) ", name[cur[0]], cur[1])
		for v := 0; v < n; v++ {
			if w[cur[0]][v] == 0 {
				continue
			}
			viaCur := cur[1] + w[cur[0]][v]
			if viaCur < dist[v] {
				dist[v] = viaCur
				heap.Push(frontier, [2]int{v, viaCur})
			}
		}
	}
	fmt.Println("\nдо T добрались за", dist[4])
}

Запустить

живой пример

class MinHeap {
  constructor(less) {
    this.a = [];
    this.less = less;
  }
  get size() { return this.a.length; }
  push(v) {
    const a = this.a;
    let i = a.push(v) - 1;
    while (i > 0 && this.less(a[i], a[(i - 1) >> 1])) {
      const p = (i - 1) >> 1;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (2 * i + 1 < a.length) {
        let c = 2 * i + 1;
        if (c + 1 < a.length && this.less(a[c + 1], a[c])) c++;
        if (!this.less(a[c], a[i])) break;
        [a[i], a[c]] = [a[c], a[i]];
        i = c;
      }
    }
    return top;
  }
}

const name = ["S", "A", "B", "C", "T"];
const edges = [[0, 1, 2], [0, 2, 5], [1, 3, 2], [3, 4, 3], [2, 4, 4]];
const n = name.length;
const w = Array.from({ length: n }, () => new Array(n).fill(0));
for (const [u, v, weight] of edges) {
  w[u][v] = weight;
  w[v][u] = weight;
}
const dist = new Array(n).fill(Infinity);
dist[0] = 0;
const frontier = new MinHeap((x, y) => x[1] < y[1]);
frontier.push([0, 0]);
let line = "порядок обработки: ";
while (frontier.size > 0) {
  const [u, d] = frontier.pop();
  if (d > dist[u]) continue;
  line += `${name[u]}(${d}) `;
  for (let v = 0; v < n; v++) {
    if (w[u][v] === 0) continue;
    const viaU = d + w[u][v];
    if (viaU < dist[v]) {
      dist[v] = viaU;
      frontier.push([v, viaU]);
    }
  }
}
console.log(line);
console.log(`до T добрались за ${dist[4]}`);

Запустить

живой пример

import heapq

name = ["S", "A", "B", "C", "T"]
edges = [(0, 1, 2), (0, 2, 5), (1, 3, 2), (3, 4, 3), (2, 4, 4)]
n = len(name)
w = [[0] * n for _ in range(n)]
for u, v, weight in edges:
    w[u][v] = w[v][u] = weight
dist = [float("inf")] * n
dist[0] = 0
frontier = [(0, 0)]                      # (дистанция, вершина): куча сравнивает по дистанции
print("порядок обработки: ", end="")
while frontier:
    d, u = heapq.heappop(frontier)
    if d > dist[u]:
        continue
    print(f"{name[u]}({d}) ", end="")
    for v in range(n):
        if w[u][v] == 0:
            continue
        via_u = d + w[u][v]
        if via_u < dist[v]:
            dist[v] = via_u
            heapq.heappush(frontier, (via_u, v))
print(f"\nдо T добрались за {dist[4]}")

Запустить

А таблицу «каждый до каждого» — кратчайшие пути между всеми парами вершин — строит не Дейкстра, а алгоритм Флойда — Уоршелла. Устроен он неожиданно просто: берут матрицу расстояний и перебирают все вершины как возможную «пересадку», спрашивая для каждой пары, не короче ли ехать через неё. Три вложенных цикла по числу вершин — отсюда и цена, O(V³). На сотне вершин это миллион шагов и совершенно не страшно, на десяти тысячах — уже триллион, и задачу решают иначе: запускают Дейкстру из каждой вершины по очереди. Отрицательные веса рёбер Флойду — Уоршеллу не мешают, лишь бы не было циклов с отрицательной суммой.

В навигаторе работает не чистый Дейкстра, а его расширение A*. Дейкстра расходится от старта кругами и до цели в ста километрах по прямой обойдёт все города в радиусе ста километров во все стороны. A* добавляет к пройденной дистанции оценку остатка до цели, например расстояние по прямой, и достаёт из очереди вершину с наименьшей суммой «пройдено плюс осталось по оценке»: волна вытягивается в сторону цели. Единственное требование к оценке: она не должна завышать настоящее расстояние, иначе алгоритм пройдёт мимо кратчайшего пути; расстояние по прямой этому требованию удовлетворяет всегда, дорога короче прямой не бывает. При нулевой оценке A* превращается обратно в Дейкстру. Код отличается одной строкой в компараторе очереди, а выигрыш в навигаторе десятикратный.

Когда задача неразрешима

Взвешенные графы приводят и к задачам, которые выглядят похоже, но решаются несравнимо тяжелее. Самая знаменитая — задача коммивояжёра: найти кратчайший маршрут, проходящий через все города ровно по разу и возвращающийся в начало. Кажется, чуть сложнее кратчайшего пути — но быстрого точного алгоритма для неё не известно: число вариантов растёт факториально, и для большого числа городов перебор за разумное время невозможен.

Такие задачи называют труднорешаемыми, в теории у них есть свои имена (NP-полные и NP-трудные), но важно следствие: идеальный ответ на практике не ищут — довольствуются приближённым, «достаточно хорошим» маршрутом, полученным эвристиками.

Как это сделано в стандартной библиотеке

Приоритетная очередь, на которой держатся и Дейкстра, и минимальный остов, в стандартной библиотеке есть: java.util.PriorityQueue. Самих алгоритмов там нет, их пишут руками поверх неё.

Внутри PriorityQueue — та самая двоичная куча, уложенная в массив. Отсюда честные сложности: offer (положить) и poll (снять минимальный) — O(log N) на всплытие и погружение, peek (посмотреть минимальный, не снимая) и size — O(1). Порядок задаёт компаратор из конструктора — в примере выше это Comparator.comparingInt(pair -> pair[1]), то есть «по дистанции».

Главная грабля — именно в Дейкстре. Алгоритм по учебнику требует операции «уменьшить дистанцию у вершины, которая уже лежит в очереди», а в PriorityQueue такой операции нет. Поменять поле у объекта, который уже внутри, нельзя: куча не заметит изменения, и её порядок сломается. remove(Object) существует, но ищет элемент линейным перебором за O(N), то есть съедает весь выигрыш.

Приоритетная очередь, на которой держатся и Дейкстра, и минимальный остов, в стандартной библиотеке есть: пакет container/heap. Самих алгоритмов там нет, их пишут руками поверх неё, а саму очередь собирают из своего среза и пяти методов, как в примерах выше.

Внутри — та самая двоичная куча, уложенная в срез. Отсюда честные сложности: heap.Push (положить) и heap.Pop (снять минимальный) — O(log N) на всплытие и погружение, вершина h[0] и Len — O(1). Порядок задаёт ваш метод Less — в примере выше он сравнивает дистанции.

Главная грабля Дейкстры во всех языках — операция «уменьшить дистанцию у вершины, которая уже лежит в очереди», и в Go она, в отличие от Java, есть: heap.Fix(h, i) восстанавливает кучу после изменения элемента с индексом i за O(log N). Плата — знать индекс: в элементе заводят поле index, а Swap обновляет его при каждом обмене; так устроен пример PriorityQueue в документации пакета. Без индекса остаётся линейный поиск за O(N), который съедает весь выигрыш.

На практике чаще делают проще, как в примере выше: очередь не правят, а дописывают. Нашли путь короче — кладут новую пару «вершина, дистанция», а когда всплывёт устаревшая копия, её пропускают, сверив дистанцию с таблицей лучших. Это и делает строка if cur[1] > dist[cur[0]] { continue }. Очередь распухает до числа рёбер, зато время остаётся O(E·log V), а кода на десяток строк меньше. Настоящее уменьшение приоритета через heap.Fix берут, когда память под дубликаты жалко: на графах в десятки миллионов рёбер.

Приоритетной очереди, на которой держатся и Дейкстра, и минимальный остов, в стандартной библиотеке JavaScript нет: её пишут сами, как MinHeap в примерах выше, или берут пакет вроде @datastructures-js/priority-queue. Самих алгоритмов тем более нет.

Внутри у самодельной очереди — та самая двоичная куча, уложенная в массив. Отсюда честные сложности: push (положить) и pop (снять минимальный) — O(log N) на всплытие и погружение, вершина a[0] и размер — O(1). Порядок задаёт функция «меньше» из конструктора — в примере выше это (x, y) => x[1] < y[1], то есть «по дистанции».

Главная грабля — именно в Дейкстре. Алгоритм по учебнику требует операции «уменьшить дистанцию у вершины, которая уже лежит в очереди», а у кучи такой операции нет. Поменять поле у объекта, который уже внутри, нельзя: куча не заметит изменения, и её порядок сломается. Найти элемент можно только линейным перебором за O(N), то есть съев весь выигрыш.

Поэтому на практике очередь не правят, а дописывают: нашли путь короче — кладут новую пару «вершина, дистанция», а когда всплывёт устаревшая копия, её просто пропускают, сверив дистанцию с таблицей лучших. Это и делает строка if (d > dist[u]) continue; в примере выше. Очередь распухает до числа рёбер, зато время остаётся O(E·log V). Соблазн заменить кучу на array.sort после каждой вставки здесь особенно опасен: это O(E·V·log V) вместо O(E·log V), и на графе дорог города Дейкстра уходит в минуты. Если настоящее уменьшение приоритета всё-таки нужно, берут кучу с индексом положения каждой вершины, пакет heap-js такое умеет, или упорядоченную структуру вроде sorted-btree на сбалансированном дереве, где элемент можно найти и удалить за O(log N).

Приоритетная очередь, на которой держатся и Дейкстра, и минимальный остов, в стандартной библиотеке есть: модуль heapq. Самих алгоритмов там нет, их пишут руками поверх него.

Внутри heapq — та самая двоичная куча, уложенная в обычный список. Отсюда честные сложности: heappush (положить) и heappop (снять минимальный) — O(log N) на всплытие и погружение, вершина heap[0] и len — O(1). Компаратора у heapq нет, поэтому порядок задают устройством элемента: в очередь кладут кортеж, а кортежи сравниваются поэлементно слева направо, в примере выше это (дистанция, вершина). Если на месте вершины лежит несравнимый объект, между ними ставят счётчик, чтобы при равных дистанциях сравнение не дошло до объекта.

Главная грабля — именно в Дейкстре. Алгоритм по учебнику требует операции «уменьшить дистанцию у вершины, которая уже лежит в очереди», а в heapq такой операции нет. Поменять кортеж внутри списка нельзя: куча не заметит изменения, и её порядок сломается. heap.remove(x) существует, потому что это обычный список, но ищет элемент линейным перебором за O(N) и после него кучу нужно чинить heapify, то есть съедает весь выигрыш.

Поэтому на практике очередь не правят, а дописывают: нашли путь короче — кладут новую пару, а когда всплывёт устаревшая копия, её просто пропускают, сверив дистанцию с таблицей лучших. Это и делает строка if d > dist[u]: continue в примере выше; документация heapq описывает тот же приём как пометку записи удалённой. Очередь распухает до числа рёбер, зато время остаётся O(E·log V). Если настоящее уменьшение приоритета всё-таки нужно, берут SortedList из sortedcontainers для пар «дистанция, вершина»: там элемент можно найти и удалить за O(log N).

Дополнительно: при первом чтении можно пропустить

Глубже: остов по Краскалу и система непересекающихся множестврасширенное

Прим растит остов от одной вершины. Краскал идёт иначе: сортирует все рёбра по весу и берёт по очереди каждое, которое не замыкает цикл. Единственный вопрос, как за O(1) понять, что две вершины уже связаны через ранее взятые рёбра. На него отвечает система непересекающихся множеств (union-find): каждая вершина хранит ссылку на «представителя» своей компоненты, find поднимается по ссылкам до корня, union подвешивает один корень под другой.

class DisjointSet {
    private final int[] parent;
    DisjointSet(int n) { parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } // сжатие пути
        return x;
    }
    boolean union(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;   // уже в одной компоненте: ребро замкнуло бы цикл
        parent[a] = b;
        return true;
    }
}

// Краскал: рёбра {weight, u, v} уже отсортированы по весу
int kruskal(int n, List<int[]> edges) {
    DisjointSet ds = new DisjointSet(n);
    int total = 0;
    for (int[] e : edges) if (ds.union(e[1], e[2])) total += e[0];
    return total;
}

type DisjointSet struct{ parent []int }

func NewDisjointSet(n int) *DisjointSet {
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	return &DisjointSet{parent}
}

func (d *DisjointSet) Find(x int) int {
	for d.parent[x] != x {
		d.parent[x] = d.parent[d.parent[x]] // сжатие пути
		x = d.parent[x]
	}
	return x
}

func (d *DisjointSet) Union(a, b int) bool {
	a, b = d.Find(a), d.Find(b)
	if a == b {
		return false // уже в одной компоненте: ребро замкнуло бы цикл
	}
	d.parent[a] = b
	return true
}

// Краскал: рёбра {вес, u, v} уже отсортированы по весу
func kruskal(n int, edges [][3]int) int {
	ds := NewDisjointSet(n)
	total := 0
	for _, e := range edges {
		if ds.Union(e[1], e[2]) {
			total += e[0]
		}
	}
	return total
}

class DisjointSet {
  constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // сжатие пути
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    a = this.find(a); b = this.find(b);
    if (a === b) return false;   // уже в одной компоненте: ребро замкнуло бы цикл
    this.parent[a] = b;
    return true;
  }
}

// Краскал: рёбра [weight, u, v] уже отсортированы по весу
function kruskal(n, edges) {
  const ds = new DisjointSet(n);
  let total = 0;
  for (const [weight, u, v] of edges) if (ds.union(u, v)) total += weight;
  return total;
}

class DisjointSet:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # сжатие пути
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        a, b = self.find(a), self.find(b)
        if a == b:
            return False    # уже в одной компоненте: ребро замкнуло бы цикл
        self.parent[a] = b
        return True


# Краскал: рёбра (вес, u, v) уже отсортированы по весу
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int:
    ds = DisjointSet(n)
    return sum(weight for weight, u, v in edges if ds.union(u, v))

Со сжатием пути (строка в find, которая переподвешивает узел через один) и объединением по рангу каждая операция стоит почти O(1), формально O(α(N)), где α растёт медленнее любого логарифма. Краскал в целом O(E log E) из-за сортировки рёбер, и он удобнее Прима на разреженных графах и там, где рёбра приходят списком.

Union-find живёт и вне графов: склейка дубликатов («если совпал email или телефон, это один клиент»), компоненты связности в один проход, проверка «в одной ли сети два узла». Везде, где надо быстро объединять группы и спрашивать «в одной ли группе», это короче и быстрее, чем обход.

Коротко

Во взвешенном графе у рёбер есть числовой вес (стоимость, длина, время), и появляются задачи оптимизации.
Минимальное остовное дерево (MST) связывает все вершины с наименьшей суммой весов; жадный алгоритм Прима добавляет самое дешёвое ребро к уже подключённой части.
Алгоритм Дейкстры находит кратчайший путь от старта: обрабатывает вершины в порядке близости, обновляя дистанции соседей; опирается на приоритетную очередь и требует неотрицательных весов.

В Java PriorityQueue не умеет уменьшать приоритет: устаревшие пары не правят, а дописывают и пропускают при выемке — O(E·log V). Нужна настоящая операция — берут TreeSet.

В Go очередь собирают на container/heap; устаревшие пары дописывают и пропускают при выемке — O(E·log V), а настоящее уменьшение приоритета даёт heap.Fix по индексу элемента.

В JavaScript приоритетной очереди нет: класс на двадцать строк или пакет; устаревшие пары дописывают и пропускают при выемке — O(E·log V); sort после каждой вставки делает Дейкстру квадратичной.

В Python очередь это heapq с кортежами (дистанция, вершина); устаревшие пары дописывают и пропускают при выемке — O(E·log V). Нужна настоящая операция — SortedList из sortedcontainers.

Коммивояжёр и гамильтоновы циклы труднорешаемы: точного быстрого алгоритма нет, их решают приближённо. Узнавать такие задачи заранее важно — перебор обречён.
Второй способ построить остов, Краскал: рёбра по весу, берём те, что не замыкают цикл; проверку за O(α(N)) даёт union-find, он же склеивает дубликаты и компоненты.
Прим верен по свойству разреза: самое дешёвое ребро через любой разрез входит в минимальный остов; на приоритетной очереди он стоит O(E·log V).
A* это Дейкстра плюс оценка остатка до цели (расстояние по прямой), которая не завышает; волна вытягивается к цели, и навигатор обходит в разы меньше вершин.

Что почитать дальше

Графы — обходы в ширину и в глубину, с которых начинается любой алгоритм на графе.
Пирамиды (кучи) — устройство приоритетной очереди, на которой держатся и Дейкстра, и остов.
Красно-чёрные деревья — упорядоченное множество, когда очереди не хватает операции «уменьшить приоритет».
Как выбрать структуру данных — сводка раздела: что брать под какую задачу.

Отработать эту тему, а не только прочитать

тест фазы «Алгоритмы и структуры данных» с зачётом

тренажёры программы: SQL, код-ревью, систем-дизайн, многопоточность, лайвкодинг, алгоритмы, инциденты, код — 1449 задач

ИИ-ментор: разбирает статью и проверяет решения