PHP இல் Disjoint Set (Union-Find Algorithm)

வெளியிடப்பட்டது: 16 பிப்ரவரி, 2025 அன்று பிற்பகல் 12:29:43 UTC

இந்த கட்டுரை டிஸ்ஜாயிண்ட் செட் தரவு கட்டமைப்பின் PHP செயல்படுத்தலைக் கொண்டுள்ளது, இது பொதுவாக குறைந்தபட்ச ஸ்பேனிங் மர வழிமுறைகளில் யூனியன்-ஃபைண்டிற்கு பயன்படுத்தப்படுகிறது.

இந்தப் பக்கம் முடிந்தவரை பலருக்கு அணுகக்கூடியதாக இருக்க வேண்டும் என்பதற்காக ஆங்கிலத்திலிருந்து இயந்திர மொழிபெயர்ப்பு செய்யப்பட்டது. துரதிர்ஷ்டவசமாக, இயந்திர மொழிபெயர்ப்பு இன்னும் முழுமையான தொழில்நுட்பமாக இல்லை, எனவே பிழைகள் ஏற்படலாம். நீங்கள் விரும்பினால், அசல் ஆங்கிலப் பதிப்பை இங்கே காணலாம்:

Disjoint Set (Union-Find Algorithm) in PHP

டிஸ்ஜாயிண்ட் செட் (பொதுவாக யூனியன்-ஃபைண்ட் அல்லது டிஸ்ஜாயிண்ட் செட் யூனியனுக்குப் பயன்படுத்தப்படுகிறது) என்பது உறுப்புகளின் பிரிவினையை டிஸ்ஜாயிண்ட் (ஒன்றுடன் ஒன்று அல்லாத) கணங்களாக நிர்வகிக்கப் பயன்படுத்தப்படும் தரவு கட்டமைப்பாகும். இது இரண்டு முக்கிய செயல்பாடுகளை திறமையாக ஆதரிக்கிறது:

கண்டுபிடி: ஒரு உறுப்பு எந்த தொகுப்பைச் சேர்ந்தது என்பதை தீர்மானிக்கிறது.
ஒன்றியம்: இரண்டு தொகுப்புகளை ஒன்றாக இணைக்கிறது.

க்ருஸ்கலின் அல்காரிதம் போன்ற குறைந்தபட்ச ஸ்பேனிங் மர வழிமுறைகளில் இந்த அமைப்பு குறிப்பாக பயனுள்ளதாக இருக்கும்.

சீரற்ற பிரமைகளை உருவாக்குவதற்குப் பயன்படுத்தப்படும் க்ருஸ்கலின் வழிமுறையின் செயல்படுத்தல் என்னிடம் உள்ளது, இது செட்களை திறம்பட ஒன்றிணைக்க டிஸ்ஜாயிண்ட் செட்டின் கீழே உள்ள PHP செயல்படுத்தலை நம்பியுள்ளது. நீங்கள் ஆர்வமாக இருந்தால், அதை இங்கே செயலில் காணலாம்: க்ருஸ்கலின் அல்காரிதம் பிரமை ஜெனரேட்டர்

எப்படியிருந்தாலும், இது எனது 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]++;
            }
        }
    }
}

வேடிக்கைக்காக பிரமைகளை உருவாக்குவதைத் தவிர, டிஸ்ஜாயிண்ட் செட் தரவு அமைப்பு நிச்சயமாக நிஜ வாழ்க்கை காட்சிகளுக்கும் பயன்படுத்தப்படலாம்.

உதாரணமாக, அதன் பயனர்களுக்கு புதிய நண்பர்களை பரிந்துரைக்க விரும்பும் ஒரு சமூக வலைப்பின்னலை கற்பனை செய்து பாருங்கள், பின்னர் இந்த நண்பர் உறவுகளுடன் ஆறு பேர் ஏற்கனவே உள்ளனர் என்று சொல்லலாம்:

1 மற்றும் 2 இருவரும் நண்பர்கள்.
2 மற்றும் 3 இருவரும் நண்பர்கள்.
4 மற்றும் 5 பேர் நண்பர்கள்.
6 பேருக்கு நண்பர்கள் இல்லை.

இந்த தனித்தனி குழுக்களுக்கு யூனியன்-ஃபைண்ட் வழிமுறையைப் பயன்படுத்தினால், பின்வருவனவற்றை நாம் கண்டுபிடிக்க வேண்டும்:

ஒரு குழுவில் 1, 2 மற்றும் 3.
இரண்டாவது குழுவில் 4 மற்றும் 5.
மூன்றாவது குழுவில் 6.

இதன் அடிப்படையில், 1 மற்றும் 3 நண்பர்களாக மாற வேண்டும் என்று பரிந்துரைப்பது அர்த்தமுள்ளதாக இருக்கும், ஏனென்றால் அவர்களுக்கு பொதுவான நபர் 2 உள்ளது.

நிச்சயமாக, இது போன்ற ஒரு சிறிய எடுத்துக்காட்டில், இந்த உண்மையை நீங்களே எளிதாகக் கண்டறிய முடியும், ஆனால் இந்த வழிமுறையின் செயல்திறன் பில்லியன் கணக்கான மக்கள் மற்றும் நண்பர் குழுக்களுக்கு சாத்தியமான அளவில் அளவிட அனுமதிக்கிறது.