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

Δημοσιεύθηκε: 16 Φεβρουαρίου 2025 στις 12:24:57 μ.μ. UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

Το Ασύνδετο σύνολο (συνήθως χρησιμοποιείται για το 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.

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