ପିଏଚପିରେ ବିଚ୍ଛିନ୍ନ ସେଟ୍ (ୟୁନିୟନ-ଫାଇଣ୍ଡ ଆଲଗୋରିଦମ୍)
ପ୍ରକାଶିତ: 12:33:28 PM UTC ଠାରେ ଫେବୃଆରୀ 16, 2025
ଏହି ପ୍ରବନ୍ଧରେ ଡିସଜୋଏଣ୍ଟ ସେଟ୍ ଡାଟା ଢାଞ୍ଚାର ଏକ ପିଏଚ୍ପି କାର୍ଯ୍ୟକାରିତା ଅଛି, ଯାହା ସାଧାରଣତଃ ସର୍ବନିମ୍ନ ବ୍ୟାପକ ଗଛ ଆଲଗୋରିଦମ୍ ରେ ୟୁନିୟନ-ଫାଇଣ୍ଡ ପାଇଁ ବ୍ୟବହୃତ ହୁଏ।
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 ଏବଂ 3 ବନ୍ଧୁ ହେବା ଉଚିତ୍ ବୋଲି ପରାମର୍ଶ ଦେବା ଅର୍ଥପୂର୍ଣ୍ଣ ହେବ, କାରଣ ସେମାନଙ୍କ ମଧ୍ୟରେ ବ୍ୟକ୍ତି 2 ସମାନ।
ଅବଶ୍ୟ, ଏହି ପରି ଏକ ଛୋଟ ଉଦାହରଣରେ, ଆପଣ ନିଜେ ଏହି ସତ୍ୟକୁ ସହଜରେ ଚିହ୍ନଟ କରିପାରିବେ, କିନ୍ତୁ ଏହି ଆଲଗୋରିଦମର ଦକ୍ଷତା ଏହାକୁ କୋଟି କୋଟି ଲୋକ ଏବଂ ବନ୍ଧୁ ଗୋଷ୍ଠୀକୁ ସମ୍ଭବ କରିବାକୁ ଅନୁମତି ଦିଏ |