Union-Find (Disjoint Set) – implementacja PHP, wykrywanie cykli, deduplicacja

Union-Find (Disjoint Set Union) to struktura danych do zarządzania zbiorami rozłącznymi. Umożliwia dwie operacje w czasie niemal O(1): sprawdzenie czy dwa elementy należą do tego samego zbioru (Find) i połączenie dwóch zbiorów (Union). Algorytm pojawia się w problemach grafowych, wykrywaniu cykli i grupowaniu elementów. W Magento 2 przydaje się przy łączeniu zduplikowanych klientów i produktów.

Idea – las drzew

Każdy element wskazuje na swojego rodzica. Korzeń drzewa wskazuje na siebie. Elementy w tym samym drzewie należą do tego samego zbioru. Find śledzi wskaźniki do korzenia. Union łączy dwa drzewa przez podpięcie jednego korzenia pod drugi.

Zbiory: {1,4,7} {2,5} {3,6,8}

parent: [_, 1, 2, 3, 1, 2, 3, 1, 3]
         0  1  2  3  4  5  6  7  8

Find(7): 7->1->1 (korzeń) = 1
Find(4): 4->1->1 (korzeń) = 1
Find(7) == Find(4) => ten sam zbiór ✓

Union(1,2): podepnij korzeń 2 pod korzeń 1
parent[2] = 1
Teraz: {1,2,4,5,7} {3,6,8}

Implementacja w PHP

<?php

declare(strict_types=1);

class UnionFind
{
    private array $parent;
    private array $rank;   // przybliżona głębokość drzewa
    private int   $count;  // liczba zbiorów

    public function __construct(int $n)
    {
        $this->count = $n;
        // Każdy element jest własnym rodzicem (osobny zbiór)
        $this->parent = range(0, $n - 1);
        $this->rank   = array_fill(0, $n, 0);
    }

    // Find z path compression - O(α(n)) amortyzowane, praktycznie O(1)
    public function find(int $x): int
    {
        if ($this->parent[$x] !== $x) {
            // Path compression: skróć ścieżkę do korzenia
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    // Union by rank - O(α(n)) amortyzowane
    public function union(int $x, int $y): bool
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX === $rootY) return false; // już w tym samym zbiorze

        // Podepnij mniejsze drzewo pod większe (by rank)
        if ($this->rank[$rootX] < $this->rank[$rootY]) {
            $this->parent[$rootX] = $rootY;
        } elseif ($this->rank[$rootX] > $this->rank[$rootY]) {
            $this->parent[$rootY] = $rootX;
        } else {
            $this->parent[$rootY] = $rootX;
            $this->rank[$rootX]++;
        }

        $this->count--;
        return true; // połączono
    }

    public function connected(int $x, int $y): bool
    {
        return $this->find($x) === $this->find($y);
    }

    public function getCount(): int { return $this->count; }
}

Zastosowanie 1 – wykrywanie cykli w grafie

<?php

// Sprawdź czy graf zawiera cykl (np. w dependency graph modułów)
function hasCycle(int $vertices, array $edges): bool
{
    $uf = new UnionFind($vertices);

    foreach ($edges as [$u, $v]) {
        if ($uf->connected($u, $v)) {
            return true; // krawędź łączy już połączone wierzchołki = cykl
        }
        $uf->union($u, $v);
    }

    return false;
}

// Sprawdź circular dependencies między modułami Magento
$moduleGraph = [
    [0, 1], // ModuleA zależy od ModuleB
    [1, 2], // ModuleB zależy od ModuleC
    [2, 3], // ModuleC zależy od ModuleD
    // [3, 0] // ModuleD zależy od ModuleA - to byłby cykl!
];

echo hasCycle(4, $moduleGraph) ? "Cykl wykryty!" : "Graf acykliczny";

Zastosowanie 2 – grupowanie zduplikowanych klientów

<?php

declare(strict_types=1);

// Zduplikowani klienci: ten sam email lub ten sam telefon = ta sama osoba
class CustomerDeduplicator
{
    public function findDuplicateGroups(array $customers): array
    {
        $n  = count($customers);
        $uf = new UnionFind($n);

        // Indeksy po emailu i telefonie
        $emailIndex = [];
        $phoneIndex = [];

        foreach ($customers as $i => $customer) {
            $email = strtolower($customer['email']);
            $phone = preg_replace('/[^0-9]/', '', $customer['phone'] ?? '');

            // Jeśli email już widziany - połącz klientów
            if (isset($emailIndex[$email])) {
                $uf->union($i, $emailIndex[$email]);
            }
            $emailIndex[$email] = $i;

            // Jeśli telefon już widziany - połącz klientów
            if ($phone && isset($phoneIndex[$phone])) {
                $uf->union($i, $phoneIndex[$phone]);
            }
            if ($phone) $phoneIndex[$phone] = $i;
        }

        // Zgrupuj według korzenia zbioru
        $groups = [];
        foreach ($customers as $i => $customer) {
            $root = $uf->find($i);
            $groups[$root][] = $customer;
        }

        // Zwróć tylko grupy z duplikatami
        return array_filter($groups, fn($g) => count($g) > 1);
    }
}

$customers = [
    ['id' => 1, 'email' => 'jan@example.com', 'phone' => '600100200', 'name' => 'Jan K.'],
    ['id' => 2, 'email' => 'jan@example.com', 'phone' => '700200300', 'name' => 'Jan Kowalski'],
    ['id' => 3, 'email' => 'anna@example.com','phone' => '600100200', 'name' => 'Anna K.'],
    ['id' => 4, 'email' => 'piotr@example.com','phone' => '500400300', 'name' => 'Piotr N.'],
];

$deduplicator = new CustomerDeduplicator();
$groups       = $deduplicator->findDuplicateGroups($customers);

// Wynik: klienci 1, 2, 3 są w jednej grupie
// (1 i 2 mają ten sam email, 1 i 3 mają ten sam telefon)
// Klient 4 jest osobny

Złożoność

α(n) to odwrotna funkcja Ackermanna – rośnie tak wolno że dla wszystkich praktycznych wartości n wynosi co najwyżej 4.

Podsumowanie

Union-Find to prosta w implementacji struktura o niemal liniowej złożoności dla dynamicznego zarządzania zbiorami. Kluczowe optymalizacje: path compression w Find i union by rank eliminują liniowe ścieżki. Klasyczne zastosowania: wykrywanie cykli w grafach, algorytm Kruskala (MST), komponenty spójne grafu i deduplicacja danych.