پی ایچ پی میں منقسم سیٹ (یونین-فائنڈ الگورتھم)

شائع شدہ: 16 فروری، 2025 کو 12:28:24 PM UTC
آخری بار اپ ڈیٹ کیا گیا: 26 جنوری، 2026 کو 10:37:02 AM UTC

اس مضمون میں ڈسجوائنٹ سیٹ ڈیٹا اسٹرکچر کی PHP امپلیمنٹیشن پیش کی گئی ہے، جو عام طور پر یونین-فائنڈ کے لیے کم از کم اسپیننگ ٹری الگورتھمز میں استعمال ہوتی ہے۔

یہ صفحہ انگریزی سے مشینی ترجمہ کیا گیا تھا تاکہ زیادہ سے زیادہ لوگوں تک اس تک رسائی ممکن بنائی جا سکے۔ بدقسمتی سے، مشینی ترجمہ ابھی تک ایک مکمل ٹیکنالوجی نہیں ہے، اس لیے غلطیاں ہو سکتی ہیں۔ اگر آپ چاہیں تو اصل انگریزی ورژن یہاں دیکھ سکتے ہیں:

Disjoint Set (Union-Find Algorithm) in PHP

ڈسجوائنٹ سیٹ (جو عام طور پر یونین-فائنڈ کے لیے استعمال ہوتا ہے، جسے ڈسجوائنٹ سیٹ یونین بھی کہا جاتا ہے) ایک ڈیٹا اسٹرکچر ہے جو عناصر کی تقسیم کو غیر منسلک (غیر اوورلیپنگ) سیٹوں میں منظم کرنے کے لیے استعمال ہوتا ہے۔ یہ دو اہم آپریشنز کو مؤثر طریقے سے سپورٹ کرتا ہے:

فائنڈ: یہ طے کرتا ہے کہ کوئی عنصر کس سیٹ سے تعلق رکھتا ہے۔
یونین: دو سیٹ کو ایک ساتھ ضم کرتا ہے۔

یہ ساخت خاص طور پر کم از کم اسپیننگ ٹری الگورتھمز میں مفید ہے، جیسے کہ کرسکل کا الگورتھم۔

میرے پاس Kruskal کے الگورتھم کا ایک نفاذ ہے جو رینڈم میزز بنانے کے لیے استعمال ہوتا ہے اور نیچے دیے گئے PHP نفاذ Disjoint Set پر انحصار کرتا ہے تاکہ سیٹس کو مؤثر طریقے سے ضم کیا جا سکے۔ اگر آپ دلچسپی رکھتے ہیں تو آپ اسے یہاں عملی طور پر دیکھ سکتے ہیں: کروسکل کا الگورتھم میز جنریٹر

خیر، یہ میرا PHP پر Disjoint Set کا نفاذ ہے:

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]++;
            }
        }
    }
}

تفریح کے لیے بھول بھلیاں بنانے کے علاوہ، Disjoint Set ڈیٹا اسٹرکچر کو حقیقی زندگی کے منظرناموں کے لیے بھی استعمال کیا جا سکتا ہے۔

مثال کے طور پر، تصور کریں کہ ایک سوشل نیٹ ورک اپنے صارفین کو نئے دوست تجویز کرنا چاہتا ہے، اور پھر فرض کریں کہ ہمارے پاس چھ ایسے لوگ ہیں جن کے یہ دوستی تعلقات پہلے سے موجود ہیں:

1 اور 2 دوست ہیں۔
2 اور 3 دوست ہیں۔
4 اور 5 دوست ہیں۔
6 کے کوئی دوست نہیں ہیں۔

یونین فائنڈ الگورتھم کو ان الگ الگ گروپوں پر لاگو کرتے ہوئے، ہمیں درج ذیل نتائج ملنے چاہئیں:

1، 2 اور 3 ایک ہی گروپ میں۔
4 اور 5 دوسرے گروپ میں۔
تیسرے گروپ میں 6۔

اس بنیاد پر، یہ بات سمجھ میں آتی ہے کہ 1 اور 3 کو دوست بننا چاہیے، کیونکہ ان میں شخص 2 مشترک ہے۔

یقینا، اس طرح کی چھوٹی مثال میں آپ خود بھی یہ بات آسانی سے دیکھ سکتے ہیں، لیکن اس الگورتھم کی کارکردگی اسے اربوں لوگوں اور دوستوں کے گروپس تک پھیلانے کی اجازت دیتی ہے۔