ପିଏଚପିରେ ବିଚ୍ଛିନ୍ନ ସେଟ୍ (ୟୁନିୟନ-ଫାଇଣ୍ଡ ଆଲଗୋରିଦମ୍)
ପ୍ରକାଶିତ: 12:33:28 PM UTC ଠାରେ ଫେବୃଆରୀ 16, 2025
ଶେଷ ଥର ପାଇଁ ଅଦ୍ୟତନ ହୋଇଥିଲା: 10:37:14 AM UTC ଠାରେ ଜାନୁଆରୀ 26, 2026
ଏହି ଆର୍ଟିକିଲରେ ଡିସଜଏଣ୍ଟ ସେଟ୍ ଡାଟା ଷ୍ଟ୍ରକଚରର ଏକ ପିଏଚପି କାର୍ଯ୍ୟାନ୍ୱୟନ ବୈଶିଷ୍ଟ୍ୟ ରହିଛି, ଯାହା ସାଧାରଣତଃ ସର୍ବନିମ୍ନ ସ୍ପାନିଂ ଟ୍ରି ଆଲଗୋରିଦମରେ ୟୁନିଅନ-ଫାଇଣ୍ଡ ପାଇଁ ବ୍ୟବହୃତ ହୁଏ ।
Disjoint Set (Union-Find Algorithm) in PHP
ଡିସଜଏଣ୍ଟ ସେଟ୍ (ସାଧାରଣତଃ ୟୁନିୟନ-ଫାଇଣ୍ଡ ଓରଫ ଡିସଜଏଣ୍ଟ ସେଟ୍ ୟୁନିଅନ ପାଇଁ ବ୍ୟବହୃତ ହୁଏ) ହେଉଛି ଏକ ଡାଟା ସଂରଚନା ଯାହା ଉପାଦାନଗୁଡ଼ିକର ବିଭାଜନକୁ ଡିସଜଏଣ୍ଟ (ଅଣ-ଓଭରଲ୍ୟାପିଂ) ସେଟ୍ ରେ ପରିଚାଳନା କରିବା ପାଇଁ ବ୍ୟବହୃତ ହୁଏ । ଏହା ଦକ୍ଷତାର ସହିତ ଦୁଇଟି ପ୍ରମୁଖ ସଞ୍ଚାଳନକୁ ସମର୍ଥନ କରେ:
- ସନ୍ଧାନ: ଏକ ସେଟ୍ କେଉଁ ସେଟ୍ ର ଅଟେ ତାହା ନିର୍ଣ୍ଣୟ କରେ ।
- ୟୁନିଅନ: ଦୁଇଟି ସେଟ୍ ଏକତ୍ର ମିଶ୍ରଣ କରେ ।
ଏହି ସଂରଚନା ସର୍ବନିମ୍ନ ବିସ୍ତାରିତ ବୃକ୍ଷ ଆଲଗୋରିଦମରେ ବିଶେଷ ଭାବରେ ଉପଯୋଗୀ ଅଟେ, ଯେପରିକି କ୍ରୁସ୍କାଲଙ୍କ ଆଲଗୋରିଦମ ।
ମୋ ପାଖରେ କ୍ରୁସ୍କାଲ୍ ର ଆଲଗୋରିଦମର ଏକ କାର୍ଯ୍ୟାନ୍ୱୟନ ଅଛି ଯାହା ଅନିୟମିତ ମେଜ୍ ସୃଷ୍ଟି କରିବା ପାଇଁ ବ୍ୟବହୃତ ହୁଏ ଯାହା ଦକ୍ଷତାର ସହିତ ସେଟ୍ ମିଶ୍ରଣ କରିବା ପାଇଁ ଡିସଜଏଣ୍ଟ ସେଟ୍ ର ନିମ୍ନ 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 ବନ୍ଧୁ ଅଟନ୍ତି।
- 2 ଏବଂ 3 ବନ୍ଧୁ ଅଟନ୍ତି।
- 4 ଏବଂ 5 ବନ୍ଧୁ ଅଟନ୍ତି ।
- 6 ର କୌଣସି ବନ୍ଧୁ ନାହାଁନ୍ତି ।
ଏହି ପୃଥକ ଗୋଷ୍ଠୀରେ ୟୁନିଅନ-ଫାଇଣ୍ଡ ଆଲଗୋରିଦମ ପ୍ରୟୋଗ କରି, ଆମେ ନିମ୍ନଲିଖିତଗୁଡ଼ିକ ଖୋଜିବା ଉଚିତ୍:
- ଗୋଟିଏ ଗୋଷ୍ଠୀରେ 1, 2 ଏବଂ 3।
- ଦ୍ୱିତୀୟ ଗୋଷ୍ଠୀରେ 4 ଏବଂ 5 ।
- ଏକ ତୃତୀୟ ଗୋଷ୍ଠୀରେ 6 ।
ଏହାକୁ ଆଧାର କରି, ଏହା ପରାମର୍ଶ ଦେବା ଅର୍ଥପୂର୍ଣ୍ଣ ହେବ ଯେ 1 ଏବଂ 3 ବନ୍ଧୁ ହେବା ଉଚିତ୍, କାରଣ ସେମାନଙ୍କର ବ୍ୟକ୍ତି 2 ମଧ୍ୟରେ ସମାନତା ଅଛି ।
ଅବଶ୍ୟ, ଏହିପରି ଏକ ଛୋଟ ଉଦାହରଣରେ, ଆପଣ ଏହି ତଥ୍ୟକୁ ସହଜରେ ନିଜେ ଚିହ୍ନିପାରିବେ, କିନ୍ତୁ ଏହି ଆଲଗୋରିଦମର ଦକ୍ଷତା ଏହାକୁ କୋଟି କୋଟି ଲୋକ ଏବଂ ବନ୍ଧୁ ଗୋଷ୍ଠୀକୁ ସମ୍ଭବ ଭାବରେ ମାପ କରିବାକୁ ଅନୁମତି ଦେଇଥାଏ ।