Disjunkt mængde (Union-Find)

Avanceret

En datastruktur der sporer elementer partitioneret i disjunkte mængder og understøtter effektive union- og find-operationer.

Kompleksitet

Operation	Tidskompleksitet
Access	`N/A`
Search	`O(α(n)) amortiseret`
Insertion	`O(1)`
Deletion	`O(α(n)) amortiseret`

Beskrivelse

Disjunkt mængde, også kaldet Union-Find, er en elegant datastruktur designet specifikt til at håndtere partitionering af elementer i ikke-overlappende mængder. Den understøtter to primære operationer: Find (hvilken mængde tilhører dette element?) og Union (sammenflet to mængder). Den klassiske implementering bruger en skov af træer hvor hvert træ repræsenterer en mængde, og roden af træet er mængdens repræsentant. To vigtige optimeringer gør disjunkt mængde ekstremt effektiv: Stikomprimering (når vi finder en nodes forælder, opdaterer vi alle noder på vejen til at pege direkte på roden) og Union by Rank (når vi sammenfletter mængder, hænger vi det mindre træ under det større). Med disse optimeringer opnår vi næsten konstant tid - mere præcist O(α(n)) hvor α er den inverse Ackermann-funktion, som vokser utroligt langsomt (α(n) < 5 for alle praktiske værdier af n). Disjunkt mængde er fundamental i grafalgoritmer som Kruskals minimum udspændende træ, netværksforbindelse, billedsegmentering, og mange andre problemer hvor vi skal gruppere elementer.

Kode Eksempel

// JavaScript Disjoint Set (Union-Find) Implementation
class DisjointSet {
  constructor(size) {
    this.parent = Array(size).fill(0).map((_, i) => i);
    this.rank = Array(size).fill(0);
    this.size = Array(size).fill(1);
    this.numSets = size;
  }

  // Find med stikomprimering
  find(x) {
    if (this.parent[x] !== x) {
      // Stikomprimering: få x til at pege direkte på rod
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // Union by rank
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    // Allerede i samme mængde
    if (rootX === rootY) {
      return false;
    }

    // Union by rank: hæng mindre træ under større træ
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
      this.size[rootY] += this.size[rootX];
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
      this.size[rootX] += this.size[rootY];
    } else {
      this.parent[rootY] = rootX;
      this.size[rootX] += this.size[rootY];
      this.rank[rootX]++;
    }

    this.numSets--;
    return true;
  }

  // Tjek om x og y er i samme mængde
  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }

  // Få størrelse af mængde der indeholder x
  getSetSize(x) {
    return this.size[this.find(x)];
  }

  // Få antal disjunkte mængder
  getNumSets() {
    return this.numSets;
  }
}

// Eksempel: Find forbundne komponenter i graf
function findConnectedComponents(n, edges) {
  const ds = new DisjointSet(n);
  
  // Behandl hver kant
  for (const [u, v] of edges) {
    ds.union(u, v);
  }
  
  return ds.getNumSets();
}

// Brug
const ds = new DisjointSet(6);
console.log('Initiale mængder:', ds.getNumSets()); // 6

ds.union(0, 1);
ds.union(1, 2);
ds.union(3, 4);

console.log('Efter unions:', ds.getNumSets()); // 3
console.log('0 og 2 forbundet?', ds.isConnected(0, 2)); // true
console.log('0 og 3 forbundet?', ds.isConnected(0, 3)); // false
console.log('Størrelse af mængde med 0:', ds.getSetSize(0)); // 3

Anvendelsesområder

•Kruskals minimum udspændende træ-algoritme
•Netværksforbindelsesproblemer
•Billedsegmentering og pixelgruppering
•Sociale netværk vennecirkler
•Labyrintgenereringsalgoritmer

Fordele

✓Næsten konstant tidsoperationer O(α(n))
✓Meget hukommelseseffektiv
✓Simpel og elegant implementering
✓Perfekt til forbindelsesproblemer
✓Let at forstå og fejlfinde

Ulemper

✗Understøtter kun union og find (begrænsede operationer)
✗Kan ikke opdele mængder efter union
✗Ikke velegnet til dynamiske mængder der ændres ofte
✗Kun for statiske elementmængder
✗Skal kende antal elementer på forhånd

Eksempler fra den virkelige verden

•Netværksforbindelse (er computer A og B forbundet?)
•Billedbehandling - find tilhørende regioner
•Kruskals MST i GPS-routing
•Sociale netværk - find vennecirkler
•Perkolationsteori i fysiksimuleringer

Relaterede strukturer

GraphTreeArrayHash Table