Ασύνδετο σύνολο (αλγόριθμος Union-Find) στην PHP

Δημοσιεύθηκε: 16 Φεβρουαρίου 2025 στις 12:24:57 μ.μ. UTC
Τελευταία ενημέρωση: 26 Ιανουαρίου 2026 στις 10:36:44 π.μ. UTC

Αυτό το άρθρο παρουσιάζει μια υλοποίηση PHP της δομής δεδομένων Disjoint Set, που χρησιμοποιείται συνήθως για Union-Find σε αλγόριθμους ελάχιστου εκτεινόμενου δέντρου.

Αυτή η σελίδα μεταφράστηκε μηχανικά από τα αγγλικά, προκειμένου να είναι προσβάσιμη σε όσο το δυνατόν περισσότερους ανθρώπους. Δυστυχώς, η αυτόματη μετάφραση δεν είναι ακόμη μια τελειοποιημένη τεχνολογία, οπότε μπορεί να προκύψουν λάθη. Αν προτιμάτε, μπορείτε να δείτε την πρωτότυπη αγγλική έκδοση εδώ:

Disjoint Set (Union-Find Algorithm) in PHP

Το Disjoint Set (που χρησιμοποιείται συνήθως για Union-Find γνωστό και ως Disjoint Set Union) είναι μια δομή δεδομένων που χρησιμοποιείται για τη διαχείριση μιας κατάτμησης στοιχείων σε ασύνδετα (μη επικαλυπτόμενα) σύνολα. Υποστηρίζει αποτελεσματικά δύο βασικές λειτουργίες:

Εύρεση: Καθορίζει σε ποιο σύνολο ανήκει ένα στοιχείο.
Ένωση: Συγχωνεύει δύο σετ μαζί.

Αυτή η δομή είναι ιδιαίτερα χρήσιμη σε αλγόριθμους ελάχιστου εκτεινόμενου δέντρου, όπως ο αλγόριθμος του Kruskal.

Έχω μια υλοποίηση του αλγορίθμου του Kruskal που χρησιμοποιείται για τη δημιουργία τυχαίων λαβύρινθων που βασίζεται στην παρακάτω υλοποίηση PHP του Disjoint Set για την αποτελεσματική συγχώνευση συνόλων. Αν σας ενδιαφέρει, μπορείτε να το δείτε σε δράση εδώ: Gennítria lavyrínthou algórithmou Kruskal

Τέλος πάντων, αυτή είναι η υλοποίηση PHP του Disjoint Set:

class DisjointSet 
{
    private $parent = [];
    private $rank   = [];

    public function __construct($size) 
    {
        for ($i = 0; $i < $size; $i++) 
        {
            $this->parent[$i]   = $i;
            $this->rank[$i]     = 0;
        }
    }

    public function find($x) 
    {
        if ($this->parent[$x] != $x) 
        {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }

        return $this->parent[$x];
    }

    public function union($x, $y) 
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX != $rootY) 
        {
            if ($this->rank[$rootX] > $this->rank[$rootY]) 
            {
                $this->parent[$rootY] = $rootX;
            }
            elseif ($this->rank[$rootX] < $this->rank[$rootY]) 
            {
                $this->parent[$rootX] = $rootY;
    
            }
            else
            {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
        }
    }
}

Εκτός από τη δημιουργία λαβύρινθων για διασκέδαση, η δομή δεδομένων Disjoint Set μπορεί σίγουρα να χρησιμοποιηθεί και για σενάρια πραγματικής ζωής.

Φανταστείτε, για παράδειγμα, ένα κοινωνικό δίκτυο που θα ήθελε να προτείνει νέους φίλους στους χρήστες του και, στη συνέχεια, ας πούμε ότι έχουμε ήδη έξι άτομα με αυτές τις φιλικές σχέσεις:

Ο 1 και ο 2 είναι φίλοι.
Ο 2 και ο 3 είναι φίλοι.
Ο 4 και ο 5 είναι φίλοι.
Το 6 δεν έχει φίλους.

Εφαρμόζοντας τον αλγόριθμο Union-Find σε αυτές τις ξεχωριστές ομάδες, θα πρέπει να βρούμε τα εξής:

1, 2 και 3 σε μία ομάδα.
4 και 5 σε μια δεύτερη ομάδα.
6 σε μια τρίτη ομάδα.

Με βάση αυτό, θα ήταν λογικό να προτείνουμε ότι ο 1 και ο 3 πρέπει να γίνουν φίλοι, επειδή έχουν κοινό το άτομο 2.

Φυσικά, σε ένα μικρό παράδειγμα όπως αυτό, θα μπορούσατε εύκολα να εντοπίσετε αυτό το γεγονός μόνοι σας, αλλά η αποτελεσματικότητα αυτού του αλγορίθμου του επιτρέπει να κλιμακωθεί σε δισεκατομμύρια ανθρώπους και ομάδες φίλων.