Minimum Spanning Tree

Nasıl düşünülür

MST, ağırlıklı yönsüz graftaki tüm düğümleri minimum toplam kenar ağırlığıyla bağlar. Bir ağaçtır (döngüsüz) ve tüm düğümleri kapsar. Temel içgörü: kenarları ağırlığa göre sırala, döngü oluşturmayacak her kenarı ekle → MST. Bu Kruskal’dır. Ölçekte döngü tespiti union-find demektir: iki uç aynı bileşendeyse kenar ekleme döngü yapar, atla.

Prim MST’yi tek bir tohumdan büyütür: kesiyi geçen kenarların (bir uç ağaçta, diğeri dışarıda) min-heap’ini tut. En ucuzu pop et, dış düğümü ekle, kenarlarını push et. Prim yoğun grafarda (E ~ V²) parlar; tüm E kenarı sıralamak israf. Seyrek graflarda (E ~ V), Kruskal’ın sıralama + union-find’i daha basit ve eşit hızlı.

Şablon şekilleri

Şekil	Temel hamle	Örnek
Kruskal	Kenar sırala; union-find döngü atla	LC 1135, LC 1584
Prim	Kesiyi geçen kenar min-heap; tohumdan büyü	LC 1168
Kısıtlı MST	Cevapta ikili arama / kenar filtrele	LC 1489
Offline MST sorguları	Sorgu + kenar sırala; union-find cevap	LC 1724

Karmaşıklık temeli

Kruskal: O(E log E) (sıralama) + yaklaşık O(E) union-find. Heap’li Prim: O((V + E) log V). Yoğun graf için heapsiz Prim O(V²).

Şablondan probleme

1. Grafın yönsüz ve ağırlıkların karşılaştırılabilir olduğunu doğrula (MST negatifi özel ele almaz).
2. Seyrek (E ~ V)? Kruskal. Yoğun (E ~ V²)? Prim.
3. Kruskal: kenarları sırala, iterasyon yap, union-find döngü atla, V-1 kenarda dur.
4. MST toplam kenar ağırlığını minimize eder, tek tek yolları değil, en kısa yol ile karıştırma.

/** MST template: Kruskal with union-find. */

export function kruskalMST(
  n: number, edges: [number, number, number][],
): { weight: number; edges: [number, number, number][] } {
  const sorted = [...edges].sort((a, b) => a[2]! - b[2]!);
  const parent = new Array<number>(n).fill(0).map((_, i) => i);
  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x]!);
    return parent[x]!;
  }
  function union(a: number, b: number): boolean {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
    return true;
  }
  let total = 0;
  const mst: [number, number, number][] = [];
  for (const e of sorted) {
    if (mst.length === n - 1) break;
    if (union(e[0]!, e[1]!)) {
      mst.push(e);
      total += e[2]!;
    }
  }
  return { weight: total, edges: mst };
}

/** MST template: Kruskal with union-find. */

export function kruskalMST(
  n: number, edges: [number, number, number][],
): { weight: number; edges: [number, number, number][] } {
  const sorted = [...edges].sort((a, b) => a[2]! - b[2]!);
  const parent = new Array<number>(n).fill(0).map((_, i) => i);
  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x]!);
    return parent[x]!;
  }
  function union(a: number, b: number): boolean {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
    return true;
  }
  let total = 0;
  const mst: [number, number, number][] = [];
  for (const e of sorted) {
    if (mst.length === n - 1) break;
    if (union(e[0]!, e[1]!)) {
      mst.push(e);
      total += e[2]!;
    }
  }
  return { weight: total, edges: mst };
}