Ayrık Küme (Disjoint-Set / Union-Find) Algoritması

1class DisjointSet {
2  parent: number[];
3  rank: number[];
4
5  constructor(size: number) {
6    this.parent = Array.from({ length: size }, (_, i) => i);
7    this.rank = Array(size).fill(0);
8  }
9
10  find(i: number, trace?: string[]): number {
11    if (this.parent[i] === i) return i;
12    
13    const root = this.find(this.parent[i], trace);
14    if (this.parent[i] !== root) {
15      if (trace) {
16        trace.push(`  [Yol Yassılaştırma] Düğüm ${i} ebeveyni güncellendi: ${this.parent[i]} -> ${root}`);
17      }
18      this.parent[i] = root; // Path compression
19    }
20    return root;
21  }
22
23  union(i: number, j: number, trace?: string[]): boolean {
24    const rootX = this.find(i, trace);
25    const rootY = this.find(j, trace);
26
27    if (rootX === rootY) {
28      if (trace) trace.push(`${i} ve ${j} zaten aynı kümede (Kök: ${rootX}).`);
29      return false;
30    }
31
32    if (trace) {
33      trace.push(`Birleştiriliyor: Kök ${rootX} (Rütbe: ${this.rank[rootX]}) ve Kök ${rootY} (Rütbe: ${this.rank[rootY]})`);
34    }
35
36    if (this.rank[rootX] < this.rank[rootY]) {
37      this.parent[rootX] = rootY;
38      if (trace) trace.push(`  Kök ${rootX} -> Kök ${rootY} altına bağlandı.`);
39    } else if (this.rank[rootX] > this.rank[rootY]) {
40      this.parent[rootY] = rootX;
41      if (trace) trace.push(`  Kök ${rootY} -> Kök ${rootX} altına bağlandı.`);
42    } else {
43      this.parent[rootY] = rootX;
44      this.rank[rootX]++;
45      if (trace) trace.push(`  Rütbeler eşit. Kök ${rootY} -> Kök ${rootX} altına bağlandı, rütbe ${this.rank[rootX]} yapıldı.`);
46    }
47    return true;
48  }
49}