PHP-യിലെ Disjoint Set (Union-Find Algorithm)

പ്രസിദ്ധീകരിച്ചത്: 2025, ഫെബ്രുവരി 16 12:32:35 PM UTC
അവസാനം അപ്ഡേറ്റ് ചെയ്തത്: 2026, ജനുവരി 26 10:37:13 AM UTC

ഈ ലേഖനത്തിൽ ഡിസ്ജോയിന്റ് സെറ്റ് ഡാറ്റാ ഘടനയുടെ ഒരു പിഎച്ച്പി നടപ്പാക്കൽ അവതരിപ്പിക്കുന്നു, ഇത് സാധാരണയായി മിനിമം സ്പാനിംഗ് ട്രീ അൽഗോരിതങ്ങളിൽ യൂണിയൻ-ഫൈൻഡിനായി ഉപയോഗിക്കുന്നു.

ഈ പേജ് കഴിയുന്നത്ര ആളുകൾക്ക് ആക്‌സസ് ചെയ്യുന്നതിനായി ഇംഗ്ലീഷിൽ നിന്ന് മെഷീൻ വിവർത്തനം ചെയ്‌തിരിക്കുന്നു. നിർഭാഗ്യവശാൽ, മെഷീൻ വിവർത്തനം ഇതുവരെ പൂർണ്ണത നേടിയിട്ടില്ലാത്ത ഒരു സാങ്കേതികവിദ്യയാണ്, അതിനാൽ പിശകുകൾ സംഭവിക്കാം. നിങ്ങൾക്ക് താൽപ്പര്യമുണ്ടെങ്കിൽ, നിങ്ങൾക്ക് ഇവിടെ യഥാർത്ഥ ഇംഗ്ലീഷ് പതിപ്പ് കാണാൻ കഴിയും:

Disjoint Set (Union-Find Algorithm) in 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 ന് കൂട്ടുകാരില്ല

ഈ പ്രത്യേക ഗ്രൂപ്പുകളിലേക്ക് യൂണിയൻ-ഫൈൻഡ് അൽഗോരിതം പ്രയോഗിക്കുമ്പോൾ, ഇനിപ്പറയുന്നവ കണ്ടെത്തണം:

ഒരു ഗ്രൂപ്പിൽ 1, 2, 3 എന്നിങ്ങനെ.
രണ്ടാമത്തെ ഗ്രൂപ്പിൽ 4, 5.
മൂന്നാം ഗ്രൂപ്പിൽ 6.

ഇതിന്റെ അടിസ്ഥാനത്തിൽ, 1 ഉം 3ഉം സുഹൃത്തുക്കളാകണമെന്ന് നിർദ്ദേശിക്കുന്നത് അർത്ഥവത്താണ്, കാരണം അവർക്ക് വ്യക്തി2പൊതുവായി ഉണ്ട്.

തീർച്ചയായും, ഇതുപോലുള്ള ഒരു ചെറിയ ഉദാഹരണത്തിൽ, നിങ്ങൾക്ക് ഈ വസ്തുത സ്വയം എളുപ്പത്തിൽ കണ്ടെത്താൻ കഴിയും, പക്ഷേ ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത കോടിക്കണക്കിന് ആളുകളിലേക്കും സുഹൃത്ത് ഗ്രൂപ്പുകളിലേക്കും പ്രായോഗികമായി സ്കെയിൽ ചെയ്യാൻ അനുവദിക്കുന്നു.