Disjoint Set (Union-Find)

Avanceret

En datastruktur der tracker elementer partitioneret i disjunkte sets og understøtter effektiv union og find operations.

Kompleksitet

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

Beskrivelse

Disjoint Set, også kaldet Union-Find, er en elegant datastruktur designet specifikt til at håndtere partitionering af elementer i non-overlapping sets. Den understøtter to primære operations: Find (hvilken set tilhører dette element?) og Union (merge to sets). Den klassiske implementation bruger en forest af træer hvor hver træ repræsenterer et set, og roden af træet er setets repræsentant. To vigtige optimizations gør Disjoint Set ekstremt effektiv: Path Compression (når vi finder en nodes parent, opdaterer vi alle nodes på vejen til at pege direkte på roden) og Union by Rank (når vi merger sets, hænger vi det mindre træ under det større). Med disse optimizations opnår vi næsten konstant tid - mere præcist O(α(n)) hvor α er inverse Ackermann function, som vokser utroligt langsomt (α(n) < 5 for alle praktiske værdier af n). Disjoint Set er fundamental i graph algorithms som Kruskal's minimum spanning tree, network connectivity, image segmentation, 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 with path compression
  find(x) {
    if (this.parent[x] !== x) {
      // Path compression: make x point directly to root
      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);

    // Already in same set
    if (rootX === rootY) {
      return false;
    }

    // Union by rank: attach smaller tree under larger tree
    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;
  }

  // Check if x and y are in same set
  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }

  // Get size of set containing x
  getSetSize(x) {
    return this.size[this.find(x)];
  }

  // Get number of disjoint sets
  getNumSets() {
    return this.numSets;
  }
}

// Eksempel: Find connected components i graph
function findConnectedComponents(n, edges) {
  const ds = new DisjointSet(n);
  
  // Process each edge
  for (const [u, v] of edges) {
    ds.union(u, v);
  }
  
  return ds.getNumSets();
}

// Eksempel: Kruskal's MST algorithm
function kruskalMST(n, edges) {
  // Sort edges by weight
  edges.sort((a, b) => a[2] - b[2]);
  
  const ds = new DisjointSet(n);
  const mst = [];
  let totalWeight = 0;
  
  for (const [u, v, weight] of edges) {
    // If adding this edge doesn't create cycle
    if (ds.union(u, v)) {
      mst.push([u, v, weight]);
      totalWeight += weight;
      
      // MST complete when we have n-1 edges
      if (mst.length === n - 1) break;
    }
  }
  
  return { mst, totalWeight };
}

// Brug
const ds = new DisjointSet(6);
console.log('Initial sets:', ds.getNumSets()); // 6

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

console.log('After unions:', ds.getNumSets()); // 3
console.log('0 and 2 connected?', ds.isConnected(0, 2)); // true
console.log('0 and 3 connected?', ds.isConnected(0, 3)); // false
console.log('Size of set with 0:', ds.getSetSize(0)); // 3

// Graph connectivity
const edges = [[0,1], [1,2], [3,4]];
console.log('Connected components:', findConnectedComponents(5, edges)); // 2

Anvendelsesområder

•Kruskal's minimum spanning tree algorithm
•Network connectivity problems
•Image segmentation og pixel grouping
•Social network friend circles
•Maze generation algorithms

Fordele

✓Næsten konstant tid operations O(α(n))
✓Meget memory efficient
✓Simpel og elegant implementation
✓Perfekt til connectivity problems
✓Let at forstå og debugge

Ulemper

✗Understøtter kun union og find (begrænsede operations)
✗Kan ikke split sets efter union
✗Ikke velegnet til dynamiske sets der ændres ofte
✗Kun for statiske element sets
✗Skal kende antal elementer på forhånd

Eksempler fra den virkelige verden

•Network connectivity (er computer A og B forbundet?)
•Image processing - find tilhørende regioner
•Kruskal's MST i GPS routing
•Social networks - find friend circles
•Percolation theory i fysik simuleringer

Relaterede strukturer

GraphTreeArrayHash Table