Struktury danychhard

Jaki problem rozwiązuje Union-Find (DSU)?

Tagi

#union-find#dsu#kruskal#connectivity

Odpowiedź

Union-Find (DSU) utrzymuje rozłączne zbiory operacjami find(x) (reprezentant) i union(a,b) (scalenie). Używa się go do spójności i w algorytmie Kruskala; z path compression + union by rank operacje są prawie O(1) amortyzowane.

class DSU {
  private parent: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }

  find(x: number): number {
    if (this.parent[x] === x) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(a: number, b: number) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra !== rb) this.parent[rb] = ra;
  }
}

Odpowiedź zaawansowana

Głębiej

Union-Find (Disjoint Set Union) utrzymuje podział elementów na rozłączne zbiory i wspiera:

find(x): zwróć reprezentanta zbioru x
union(a, b): scal dwa zbiory

Dwie kluczowe optymalizacje:

path compression (spłaszczanie drzew podczas find)
union by rank/size (podpinanie mniejszego drzewa pod większe)

…sprawiają, że operacje są praktycznie stałokosztowe dla realnych danych: O(alpha(n)) amortyzowane (odwrotność funkcji Ackermanna, rośnie ekstremalnie wolno).

Zastosowania

Zapytania o spójność w grafie nieskierowanym: czy u i v są połączone?
Kruskal (MST): podczas wybierania krawędzi scalasz zbiory, a cykle wykrywasz przez find.
Grupowanie/klastrowanie (scalanie po ograniczeniach).

Przykłady

class DSU {
  private parent: number[]
  private size: number[]

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.size = Array.from({ length: n }, () => 1)
  }

  find(x: number): number {
    if (this.parent[x] === x) return x
    this.parent[x] = this.find(this.parent[x])
    return this.parent[x]
  }

  union(a: number, b: number) {
    let ra = this.find(a)
    let rb = this.find(b)
    if (ra === rb) return
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]
    this.parent[rb] = ra
    this.size[ra] += this.size[rb]
  }
}

Typowe pułapki

Brak union by rank/size (wydajność może spaść).

Powiązane pytania

Algorytmy

Kruskal vs Prim: jaka jest główna różnica i typowe struktury danych?

#mst#kruskal#prim

Algorytmy

Kruskal vs Prim dla MST — czym się różnią?

#mst#kruskal#prim