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

Повне пояснення

Коротке пояснення

Алгоритм Крускала шукає мінімальне остовне дерево, вибираючи ребра з найменшою вагою без створення циклів.

Аналогія

Уявіть, що ви хочете з’єднати міста дорогами так, щоб витрати були мінімальними і не було замкнутих циклів; Крускал вибирає найдешевші дороги, поки не з’єднав усі міста.

Коли застосовувати

• Зважений граф з незв’язаними вершинами.
• Потрібно мінімізувати суму ваг у з’єднанні всіх вершин.
• Граф не має зайвих циклів у кінцевому результаті.
• Кількість ребер достатня для побудови дерева (|E| ≥ |V|-1).
• Потрібна швидка реалізація без складних структурування даних.

Кроки алгоритму

1. Сортувати усі ребра за зростанням ваги.
2. Ініціалізувати кожну вершину як окремий компонент (Union‑Find).
3. Проходити по відсортованих ребрах.
4. Якщо вершини ребра належать різним компонентам, додати ребро до дерева і об’єднати компоненти.
5. Продовжувати, доки не буде |V|-1 ребер у дереві.

Візуальна інтуїція (текстова)

Вершини: A B C D
Ребра (вага): AB(1), AC(3), AD(4), BC(2), CD(5)

Сортування: AB, BC, AC, AD, CD

Крок 1: AB → додаємо (A,B)
Крок 2: BC → додаємо (B,C) – A,B,C у одному компоненті
Крок 3: AC → пропускаємо (цикл)
Крок 4: AD → додаємо (A,D) – всі вершини з’єднані
Результат: дерево зі сторонами AB, BC, AD (сумарна вага 1+2+4=7)

Складність

• Час: O(E log E) через сортування ребер; Union‑Find з path compression дає O(E α(V)).
• Пам’ять: O(V+E) для зберігання графу, списку ребер і структури Union‑Find.

Код (js)

// Клас для структури Union‑Find (Disjoint Set Union)
class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // ініціалізуємо кожну вершину як власний батько
    this.rank = Array(n).fill(0); // ранг для оптимізації об’єднання
  }

  find(x) {
    // рекурсивний пошук батька з path compression
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // зменшуємо шлях
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // вже в одному компоненті
    // об’єднуємо за рангом
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX] += 1;
    }
    return true; // об’єднання успішне
  }
}

// Функція Крускала: приймає кількість вершин і масив ребер [u, v, weight]
function kruskal(numVertices, edges) {
  // Крок 1: сортування ребер за вагою
  edges.sort((a, b) => a[2] - b[2]);

  const dsu = new DSU(numVertices);
  const mst = []; // мінімальне остовне дерево
  let totalWeight = 0;

  // Крок 2: перебір відсортованих ребер
  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) { // якщо вершини в різних компонентах
      mst.push([u, v, w]); // додаємо ребро до MST
      totalWeight += w;
    }
  }

  return { mst, totalWeight };
}

// Тестовий приклад
const vertices = 4; // A=0, B=1, C=2, D=3
const edges = [
  [0, 1, 1], // AB
  [0, 2, 3], // AC
  [0, 3, 4], // AD
  [1, 2, 2], // BC
  [2, 3, 5]  // CD
];
const result = kruskal(vertices, edges);
console.log(result.mst); // очікуваний результат: [[0,1,1],[1,2,2],[0,3,4]]
console.log(result.totalWeight); // очікуваний результат: 7

Типові помилки і поради

1. Не сортувати ребра – алгоритм працює лише з відсортованим списком.
2. Використовувати звичайний масив замість Union‑Find – це призведе до O(V E) часу.
3. Забути про цикли – без Union‑Find можна випадково додати ребро, що створює цикл.
4. Неправильний індекс вершини – у JS масиви починаються з 0, тому переконайтеся, що вершини позначені відповідно.
5. Не обробляти випадок, коли граф роз’єднаний – алгоритм поверне часткове дерево; перевірте, чи кількість ребер = V‑1.

Перевір себе

1. Яка складність сортування ребер у Крускалі?
2. Для чого потрібен Union‑Find у цьому алгоритмі?