کروسکل کا الگورتھم میز جنریٹر

کروسکل کا الگورتھم ایک کم سے کم پھیلا ہوا درخت الگورتھم ہے جسے بھول بھلیوں کی پیداوار کے لئے اپنایا جاسکتا ہے۔ یہ کامل بھول بھلیاں پیدا کرنے کے لئے خاص طور پر مؤثر ہے. کروسکل کے الگورتھم کا متبادل پریم کا الگورتھم ہے ، جو کم سے کم پھیلا ہوا درخت الگورتھم بھی ہے ، لیکن چونکہ وہ ایک جیسی بھول بھلیاں پیدا کرتے ہیں اور کروسکل کے رنز تیزی سے پیدا کرتے ہیں ، لہذا میں نے پرائم کو نافذ کرنے کی زحمت نہیں اٹھائی ہے۔

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

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

کروسکل کے الگورتھم کے بارے میں

کروسکل کا الگورتھم جوزف برنارڈ کروسکل جونیئر نے تیار کیا تھا، جو ایک امریکی ریاضی دان، شماریات دان اور کمپیوٹر سائنسدان تھے۔ انہوں نے پہلی بار 1956 میں اپنے مقالے "گراف کے سب سے چھوٹے پھیلنے والے سب ٹری اور سفری سیلز مین کے مسئلے پر" میں الگورتھم کی وضاحت کی۔

الگورتھم کو گراف کے کم سے کم پھیلے ہوئے درخت (ایم ایس ٹی) کو تلاش کرنے کے لئے ڈیزائن کیا گیا ہے ، اس بات کو یقینی بنانے کے لئے کہ تمام سرے سائیکلوں سے بچتے ہوئے کم سے کم ممکنہ کل کنارے کے وزن سے منسلک ہیں۔

کروسکل کا الگورتھم بھولبھلی نسل کے لئے کیسے کام کرتا ہے

مرحلہ 1: شروع کریں

• بھول بھلیوں میں ہر سیل کو ایک علیحدہ سیٹ (ایک انوکھا جزو) کے طور پر سمجھیں۔
• ملحقہ خلیوں کے درمیان تمام دیواروں کو ممکنہ کناروں کے طور پر درج کریں۔

مرحلہ 2: دیواروں کو ترتیب دیں

• دیواروں کو تبدیل کریں یا بے ترتیب ترتیب دیں۔ اگر اسے ایک حقیقی کروسکل کے الگورتھم کے طور پر لاگو کیا جاتا ہے تو ، دیواروں کو بے ترتیب ترتیب میں ترتیب دیں (کیونکہ بھول بھلیوں کی پیداوار کو وزن کی ضرورت نہیں ہوتی ہے)۔

مرحلہ 3: پروسیس دیواریں

• ہلتی ہوئی دیواروں کے ذریعے سفر کریں۔
• اگر دیوار کے ذریعہ تقسیم کردہ دو خلیات مختلف سیٹوں سے تعلق رکھتے ہیں (یعنی ، وہ ابھی تک بھول بھلی میں منسلک نہیں ہیں) تو دیوار کو ہٹا دیں اور سیٹوں کو ضم کردیں۔
• اگر وہ پہلے سے ہی ایک ہی سیٹ میں ہیں تو ، دیوار کو چھوڑ دیں (سائیکلوں سے بچنے کے لئے)۔

مرحلہ 4: تکمیل تک جاری رکھیں

• اس عمل کو اس وقت تک دہرائیں جب تک کہ تمام خلیات منسلک نہ ہوجائیں ، جس سے ایک ہی پھیلا ہوا درخت بن جائے۔
• آخر میں ، ہر سیل لوپس یا الگ تھلگ حصوں کے بغیر دوسروں سے جڑا ہوا ہے۔

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