Алгоритм Крускала для графів з вагами

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

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

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

Аналогія

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

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

• Задача про мінімальне остовне дерево у зваженому графі.
• Граф необмежений, може бути роз’єднаним (тоді алгоритм дає мінімальний остов кожної компоненти).
• Потрібна найменша сума ваг.
• Кількість ребер не надто велика, щоб сортування було ефективним.

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

1. Сортувати всі ребра за зростанням ваги.
2. Створити структуру «з’єднані компоненти» (Union‑Find).
3. Для кожного ребра у відсортованому списку:
   • Якщо вершини різних компонент, додати ребро до дерева і об’єднати компоненти.
   • Якщо вершини однієї компонент, пропустити ребро (цикл).
4. Після проходу отримати мінімальне остовне дерево.

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

Вхід: 5 вершин, 7 ребер
Сортування: (a,b,1) (b,c,2) (c,d,3) (d,e,4) (a,c,5) (b,d,6) (c,e,7)
Крок 1: додати (a,b,1) → дерево
Крок 2: додати (b,c,2) → дерево
Крок 3: додати (c,d,3) → дерево
Крок 4: додати (d,e,4) → дерево (завершено)

Складність

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

Код (js)

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

  // Знаходимо корінь компоненти з шляхом стиснення
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // стиснення
    }
    return this.parent[x];
  }

  // Об’єднуємо дві компоненти, повертає true якщо об’єднання відбулося
  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;
  }
}

// Функція Крускала: повертає масив ребер мінімального остовного дерева
function kruskal(vertices, edges) {
  // Крок 1: сортування ребер за зростанням ваги
  const sortedEdges = edges.slice().sort((a, b) => a.weight - b.weight);

  const uf = new UnionFind(vertices); // створюємо структуру для V вершини
  const mst = []; // масив результату

  for (const edge of sortedEdges) {
    const { from, to, weight } = edge;
    // Крок 3: додаємо ребро, якщо не створює цикл
    if (uf.union(from, to)) {
      mst.push(edge);
    }
  }

  return mst;
}

// Тестовий приклад
const vertices = 5; // кількість вершин (0…4)
const edges = [
  { from: 0, to: 1, weight: 1 },
  { from: 1, to: 2, weight: 2 },
  { from: 2, to: 3, weight: 3 },
  { from: 3, to: 4, weight: 4 },
  { from: 0, to: 2, weight: 5 },
  { from: 1, to: 3, weight: 6 },
  { from: 2, to: 4, weight: 7 }
];

console.log(kruskal(vertices, edges)); // очікуваний результат: [{from:0,to:1,w:1},{from:1,to:2,w:2},{from:2,to:3,w:3},{from:3,to:4,w:4}]

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

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

Перевір себе

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