PHP-യിലെ Disjoint Set (Union-Find Algorithm)
പ്രസിദ്ധീകരിച്ചത്: 2025, ഫെബ്രുവരി 16 12:32:35 PM UTC
ഈ ലേഖനം ഡിസ്ജോയിന്റ് സെറ്റ് ഡാറ്റാ ഘടനയുടെ പിഎച്ച്പി നടപ്പാക്കൽ അവതരിപ്പിക്കുന്നു, ഇത് യൂണിയൻ-ഫൈൻഡിനായി മിനിമം സ്പാനിംഗ് ട്രീ അൽഗോരിതങ്ങളിൽ ഉപയോഗിക്കുന്നു.
Disjoint Set (Union-Find Algorithm) in PHP
മൂലകങ്ങളുടെ വിഭജനം ഡിസ്ജോയിന്റ് (ഓവർലാപ്പ് ചെയ്യാത്ത) സെറ്റുകളായി കൈകാര്യം ചെയ്യാൻ ഉപയോഗിക്കുന്ന ഒരു ഡാറ്റാ ഘടനയാണ് ഡിസ്ജോയിന്റ് സെറ്റ് (സാധാരണയായി യൂണിയൻ-ഫൈൻഡ് എ.കെ.എ. ഡിസ്ജോയിന്റ് സെറ്റ് യൂണിയൻ). ഇത് രണ്ട് പ്രധാന പ്രവർത്തനങ്ങളെ കാര്യക്ഷമമായി പിന്തുണയ്ക്കുന്നു:
- കണ്ടെത്തുക: ഒരു മൂലകം ഏത് സെറ്റിൽ പെട്ടതാണെന്ന് നിർണ്ണയിക്കുന്നു.
- യൂണിയൻ: രണ്ട് സെറ്റുകൾ ഒരുമിച്ച് ലയിപ്പിക്കുന്നു.
ക്രുസ്കലിന്റെ അൽഗോരിതം പോലുള്ള മിനിമം സ്പാനിംഗ് ട്രീ അൽഗോരിതങ്ങളിൽ ഈ ഘടന പ്രത്യേകിച്ചും ഉപയോഗപ്രദമാണ്.
സെറ്റുകൾ കാര്യക്ഷമമായി ലയിപ്പിക്കുന്നതിന് ഡിസ്ജോയിന്റ് സെറ്റിന്റെ ചുവടെയുള്ള പിഎച്ച്പി നടപ്പാക്കലിനെ ആശ്രയിക്കുന്ന റാൻഡം മാസ് സൃഷ്ടിക്കുന്നതിന് ഉപയോഗിക്കുന്ന ക്രുസ്കലിന്റെ അൽഗോരിതത്തിന്റെ നടപ്പാക്കൽ എന്റെ പക്കലുണ്ട്. നിങ്ങൾക്ക് താൽപ്പര്യമുണ്ടെങ്കിൽ, നിങ്ങൾക്ക് അത് ഇവിടെ പ്രവർത്തനത്തിൽ കാണാൻ കഴിയും: ക്രുസ്കലിന്റെ അൽഗോരിതം മെയ്സ് ജനറേറ്റർ
എന്തായാലും, ഇത് ഡിസ്ജോയിന്റ് സെറ്റിന്റെ എന്റെ പിഎച്ച്പി നടപ്പാക്കലാണ്:
{
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 ഉം കൂട്ടുകാരാണ്.
- രണ്ടും മൂന്നും സുഹൃത്തുക്കളാണ്.
- നാലും അഞ്ചും സുഹൃത്തുക്കളാണ്.
- 6-ന് കൂട്ടുകാരില്ല.
ഈ പ്രത്യേക ഗ്രൂപ്പുകളിലേക്ക് യൂണിയൻ-ഫൈൻഡ് അൽഗോരിതം പ്രയോഗിക്കുമ്പോൾ, ഞങ്ങൾ ഇനിപ്പറയുന്നവ കണ്ടെത്തണം:
- ഒരു ഗ്രൂപ്പിൽ 1, 2, 3.
- രണ്ടാമത്തെ ഗ്രൂപ്പിൽ 4 ഉം 5 ഉം.
- മൂന്നാമത്തെ ഗ്രൂപ്പിൽ 6 പേർ.
ഇതിന്റെ അടിസ്ഥാനത്തിൽ, 1 ഉം 3 ഉം സുഹൃത്തുക്കളാകണമെന്ന് നിർദ്ദേശിക്കുന്നത് അർത്ഥവത്താണ്, കാരണം അവർക്ക് പൊതുവായ വ്യക്തി 2 ഉണ്ട്.
തീർച്ചയായും, ഇതുപോലുള്ള ഒരു ചെറിയ ഉദാഹരണത്തിൽ, നിങ്ങൾക്ക് ഈ വസ്തുത എളുപ്പത്തിൽ കണ്ടെത്താൻ കഴിയും, പക്ഷേ ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത ഇത് കോടിക്കണക്കിന് ആളുകളിലേക്കും സൗഹൃദ ഗ്രൂപ്പുകളിലേക്കും വ്യാപിപ്പിക്കാൻ അനുവദിക്കുന്നു.