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

வெளியிடப்பட்டது: 16 பிப்ரவரி, 2025 அன்று பிற்பகல் 12:29:43 UTC
கடைசியாகப் புதுப்பிக்கப்பட்டது: 26 ஜனவரி, 2026 அன்று AM 10:37:08 UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

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

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

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

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

எப்படியிருந்தாலும், இது டிஸ்ஜாய்ட் செட்டின் எனது PHP செயல்படுத்தல்:

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 க்கு நண்பர்கள் இல்லை.

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

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

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

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