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

شائع شدہ: 16 فروری، 2025 کو 12:28:24 PM 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 مشترک ہے۔

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