سب کو سلام۔
اس نوٹ میں، میں نے کمپیوٹر سائنس میں گراف کو ذخیرہ کرنے کے لیے استعمال ہونے والے مرکزی ڈیٹا ڈھانچے کی فہرست بنانے کا فیصلہ کیا، اور میں اس طرح کے کچھ اور ڈھانچے کے بارے میں بھی بات کروں گا جو کسی نہ کسی طرح میرے لیے "کرسٹالائز" ہیں۔
تو، چلو شروع کرتے ہیں. لیکن شروع ہی سے نہیں - میرے خیال میں ہم سب پہلے ہی جانتے ہیں کہ گراف کیا ہے اور وہ کیا ہیں (ہدایت شدہ، غیر ہدایت شدہ، وزنی، غیر وزنی، متعدد کناروں اور لوپس کے ساتھ یا اس کے بغیر)۔
تو چلو چلتے ہیں. ہمارے پاس "گراف اسٹوریج" کے لیے ڈیٹا ڈھانچے کے کیا اختیارات ہیں؟
1. میٹرکس ڈیٹا سٹرکچرز
1.1 ملحقہ میٹرکس۔ ملحقہ میٹرکس ایک میٹرکس ہے جہاں قطار اور کالم کی سرخیاں گراف کے عمودی نمبروں سے مطابقت رکھتی ہیں، اور اس کے عناصر میں سے ہر ایک کی قدر کا تعین عمودی کے درمیان کناروں کی موجودگی یا عدم موجودگی سے کیا جاتا ہے۔ i اور j (یہ واضح ہے کہ غیر ہدایت شدہ گراف کے لیے ایسا میٹرکس سڈول ہو گا، یا ہم اس بات پر متفق ہو سکتے ہیں کہ ہم تمام اقدار کو صرف مرکزی اخترن کے اوپر محفوظ کرتے ہیں)۔ غیر وزنی گرافس کے لیے، a(i،j) کو i سے j تک کناروں کی تعداد کے حساب سے سیٹ کیا جا سکتا ہے (اگر ایسا کوئی کنارہ نہیں ہے، تو a(i،j)= 0)، اور وزن والے گرافس کے لیے بھی وزن کے حساب سے (کل وزن) مذکورہ کناروں کا۔
1.2 واقعاتی میٹرکس۔ اس صورت میں، ہمارا گراف بھی ایک ٹیبل میں محفوظ ہوتا ہے جس میں، ایک اصول کے طور پر، قطار کے نمبر اس کے عمودی نمبروں کے مساوی ہوتے ہیں، اور کالم کے نمبر پہلے سے نمبر والے کناروں کے مساوی ہوتے ہیں۔ اگر کوئی چوٹی اور کنارہ ایک دوسرے کے ساتھ واقع ہیں، تو متعلقہ سیل میں ایک غیر صفر قدر لکھی جاتی ہے (غیر ہدایت شدہ گرافس کے لیے، 1 لکھا جاتا ہے اگر عمودی اور کنارے واقع ہیں، اورینٹڈ گرافس کے لیے - "1" اگر کنارے چوٹی سے "باہر نکلتا ہے" اور "-1" اگر اس میں "شامل ہے" (یہ یاد رکھنا کافی آسان ہے، کیونکہ "مائنس" کا نشان بھی نمبر "-1" میں "شامل" لگتا ہے)۔ وزن والے گرافس کے لیے، دوبارہ، 1 اور -1 کے بجائے، آپ کنارے کا کل وزن بتا سکتے ہیں۔
2. گنتی کے اعداد و شمار کے ڈھانچے
2.1 ملحقہ فہرست۔ ٹھیک ہے، یہاں سب کچھ آسان لگتا ہے. گراف کا ہر ورٹیکس، عام طور پر، کسی بھی گنتی کے ڈھانچے (فہرست، ویکٹر، سرنی، ...) کے ساتھ منسلک کیا جا سکتا ہے، جو دیئے گئے ایک سے ملحق تمام عمودی حصوں کے اعداد کو محفوظ کرے گا۔ ڈائریکٹڈ گرافس کے لیے، ہم ایسی فہرست میں صرف ان ہی چوٹیوں کو شامل کریں گے جن میں فیچر کے چوٹی سے "ڈائریکٹڈ" کنارہ ہوتا ہے۔ وزن والے گراف کے لیے عمل درآمد زیادہ پیچیدہ ہوگا۔
2.2 پسلیوں کی فہرست۔ کافی مقبول ڈیٹا ڈھانچہ۔ کناروں کی فہرست، جیسا کہ کیپٹن اوبیوینس ہمیں بتاتا ہے، دراصل گراف کے کناروں کی ایک فہرست ہے، جن میں سے ہر ایک کو شروع کی چوٹی، اختتامی ورٹیکس کے ذریعے مخصوص کیا جاتا ہے (غیر ہدایت شدہ گراف کے لیے یہاں ترتیب اہم نہیں ہے، حالانکہ آپ یکجا کرنے کے لیے کر سکتے ہیں۔ مختلف اصولوں کا استعمال کریں، مثال کے طور پر، چوٹیوں کو بڑھانے کے لیے بتانا) اور وزن (صرف وزن والے گراف کے لیے)۔
آپ اوپر دی گئی میٹرکس کی فہرستوں کو مزید تفصیل سے دیکھ سکتے ہیں (اور مثالوں کے ساتھ)، مثال کے طور پر، .
2.3 ملحقہ صف۔ سب سے عام ڈھانچہ نہیں۔ اس کے بنیادی طور پر، یہ ایک گنتی کے ڈھانچے (سرنی، ویکٹر) میں ملحقہ فہرستوں کی "پیکنگ" کی ایک شکل ہے۔ پہلے n (گراف کے عمودی عمودی کی تعداد کے مطابق) ایسی صف کے عناصر میں ایک ہی صف کے ابتدائی اشاریے ہوتے ہیں، جس سے شروع ہونے والے ایک سے متصل تمام عمودی قطار میں لکھے جاتے ہیں۔
یہاں مجھے سب سے زیادہ قابل فہم (اپنے لیے) وضاحت ملی:
3. ملحقہ ویکٹر اور ایسوسی ایٹیو ملحقہ صف
یہ پتہ چلا کہ ان لائنوں کے مصنف، ایک پیشہ ور پروگرامر نہیں ہیں، لیکن جو وقتا فوقتا گرافوں سے نمٹتے ہیں، اکثر کناروں کی فہرستوں سے نمٹتے ہیں۔ درحقیقت، یہ آسان ہے اگر گراف میں متعدد لوپس اور کنارے ہوں۔ اور اس طرح، کناروں کی کلاسک فہرستوں کی ترقی میں، میں ان کی "ترقی/برانچ/ترمیم/میوٹیشن" پر توجہ دینے کی تجویز کرتا ہوں، یعنی: ملحقہ ویکٹر اور ملحقہ ملحقہ صف۔
3.1 ملحقہ ویکٹر
کیس (a1): غیر وزنی گراف
ہم ایک غیر وزنی گراف کے لیے ملحقہ ویکٹر کو کال کریں گے جو عدد کے یکساں عدد (a[2i]، a[2i+1]،...، جہاں i کا نمبر c 0 ہے) کا ترتیب دیا گیا سیٹ، جس میں نمبروں کا ہر جوڑا a[2i] ہے، a[2i+1] بالترتیب a[2i] اور a[2i+1] عمودی کے درمیان گراف کے کنارے کی وضاحت کرتا ہے۔
اس ریکارڈنگ فارمیٹ میں اس بارے میں معلومات موجود نہیں ہے کہ آیا گراف کو ڈائریکٹ کیا گیا ہے (دونوں آپشنز ممکن ہیں)۔ ڈائیگراف فارمیٹ کا استعمال کرتے وقت، کنارے کو a[2i] سے a[2i+1] کی طرف ڈائریکٹ سمجھا جاتا ہے۔ یہاں اور نیچے: غیر ہدایت شدہ گرافس کے لیے، اگر ضروری ہو تو، ریکارڈنگ عمودی ترتیب کے لیے تقاضے لاگو کیے جاسکتے ہیں (مثال کے طور پر، یہ کہ اس کو تفویض کردہ نمبر کی کم قیمت والا چوٹی پہلے آتا ہے)۔
C++ میں، std::vector کا استعمال کرتے ہوئے ملحقہ ویکٹر کی وضاحت کرنے کا مشورہ دیا جاتا ہے، اس لیے اس ڈیٹا ڈھانچے کا نام۔
کیس (a2): غیر وزنی گراف، کنارے کے وزن عددی ہیں۔
کیس (a1) کے ساتھ مشابہت کے ساتھ، ہم عدد کے عدد (a[3i]، a[3i+1]، a[3i+2] کے ترتیب شدہ سیٹ (متحرک صف) کے ساتھ عددی کنارے کے وزن والے گراف کے لیے ملحقہ ویکٹر کو کہتے ہیں۔ ...، جہاں i کا نمبر c 0 ہے)، جہاں نمبروں کا ہر ایک "ٹرپلٹ" a[3i]، a[3i+1]، a[3i+2] عمودی نمبروں کے درمیان گراف کا ایک کنارہ بتاتا ہے a[3i] اور بالترتیب a[3i+1]، اور قدر a [3i+2] اس کنارے کا وزن ہے۔ اس طرح کے گراف کو یا تو ہدایت کی جا سکتی ہے یا نہیں۔
کیس (b): غیر وزنی گراف، غیر عددی کنارے کا وزن
چونکہ متضاد عناصر کو ایک صف (ویکٹر) میں ذخیرہ کرنا ناممکن ہے، مثال کے طور پر، درج ذیل عمل درآمد ممکن ہے۔ گراف ویکٹرز کے ایک جوڑے میں محفوظ ہوتا ہے، جس میں پہلا ویکٹر گراف کا ملحقہ ویکٹر ہوتا ہے بغیر وزن کی وضاحت کیے، اور دوسرے ویکٹر میں متعلقہ وزن ہوتا ہے (C++: std::pair کے لیے ممکنہ نفاذ )۔ اس طرح، پہلے ویکٹر کے اشاریہ 2i، 2i+1 کے تحت عمودی کے جوڑے کے ذریعے بیان کردہ کنارے کے لیے، وزن دوسرے ویکٹر کے انڈیکس i کے تحت عنصر کے برابر ہوگا۔
ویسے یہ کیوں ضروری ہے؟
ٹھیک ہے، ان لائنوں کے مصنف نے اسے بہت سے مسائل کے حل کے لیے کافی مفید پایا۔ ٹھیک ہے، رسمی نقطہ نظر سے، مندرجہ ذیل فوائد ہوں گے:
- ملحقہ ویکٹر، کسی بھی دوسرے "شماری" ڈھانچے کی طرح، کافی کمپیکٹ ہے، ملحقہ میٹرکس (ویرل گراف کے لیے) سے کم میموری لیتا ہے، اور اس پر عمل درآمد نسبتاً آسان ہے۔
- گراف کے عمودی، اصولی طور پر، منفی نمبروں سے بھی نشان زد کیے جا سکتے ہیں۔ اگر اس طرح کی "تبدیلی" کی ضرورت ہو تو کیا ہوگا؟
- گراف مختلف وزن (مثبت، منفی، یہاں تک کہ صفر) کے ساتھ متعدد کناروں اور متعدد لوپس پر مشتمل ہوسکتے ہیں۔ یہاں کوئی پابندیاں نہیں ہیں۔
- آپ کناروں کو مختلف خصوصیات بھی تفویض کر سکتے ہیں - لیکن اس پر مزید کے لیے، سیکشن 4 دیکھیں۔
تاہم، یہ تسلیم کرنا ضروری ہے کہ اس "فہرست" کا مطلب کنارے تک فوری رسائی نہیں ہے۔ اور یہاں Associative Adjacency Array بچاؤ کے لیے آتا ہے، جس پر ذیل میں بحث کی گئی ہے۔
3.2 ایسوسی ایٹیو ملحقہ صف
لہذا، اگر کسی مخصوص کنارے تک رسائی، اس کا وزن اور دیگر خواص ہمارے لیے اہم ہیں، اور یادداشت کے تقاضے ہمیں ملحقہ میٹرکس استعمال کرنے کی اجازت نہیں دیتے ہیں، تو آئیے سوچتے ہیں کہ ہم اس مسئلے کو حل کرنے کے لیے ملحقہ ویکٹر کو کیسے تبدیل کر سکتے ہیں۔ لہذا، کلید گراف کا ایک کنارہ ہے، جسے عدد کے ترتیب شدہ جوڑے کے طور پر بیان کیا جا سکتا ہے۔ یہ کیسا لگتا ہے؟ کیا یہ ایک ایسوسی ایٹیو صف میں کلید نہیں ہے؟ اور اگر ایسا ہے تو ہم اس پر عمل کیوں نہیں کرتے؟ آئیے ہمارے پاس ایک ایسوسی ایٹیو سرنی ہے جہاں ہر کلید - عدد کا ایک ترتیب شدہ جوڑا - ایک قدر سے منسلک ہوگا - ایک عدد یا ایک حقیقی عدد جو کنارے کا وزن بتاتا ہے۔ C++ میں، std::map کنٹینر (std::map) کی بنیاد پر اس ڈھانچے کو نافذ کرنے کا مشورہ دیا جاتا ہے۔ ، int> یا std::map , double>)، یا std::multimap اگر ایک سے زیادہ کناروں کی توقع ہے۔ ٹھیک ہے، ہمارے پاس گراف کو ذخیرہ کرنے کے لیے ایک ڈھانچہ ہے جو "میٹرکس" ڈھانچے سے کم میموری لیتا ہے، متعدد لوپس اور کناروں کے ساتھ گراف کی وضاحت کر سکتا ہے، اور عمودی نمبروں کی غیر منفییت کے لیے سخت تقاضے بھی نہیں ہیں (مجھے نہیں معلوم کس کو اس کی ضرورت ہے، لیکن پھر بھی)۔
4. ڈیٹا ڈھانچہ بھرا ہوا ہے، لیکن کچھ غائب ہے۔
اور یہ سچ ہے: متعدد مسائل کو حل کرتے وقت، ہمیں گراف کے کناروں پر کچھ خصوصیات تفویض کرنے کی ضرورت پڑ سکتی ہے اور اس کے مطابق، انہیں ذخیرہ کرنا پڑتا ہے۔ اگر ان خصوصیات کو غیر واضح طور پر انٹیجرز تک کم کرنا ممکن ہے، تو ملحقہ ویکٹر اور ایسوسی ایٹیو ملحقہ سرنی کے توسیعی ورژن کا استعمال کرتے ہوئے ایسے "اضافی خصوصیات کے ساتھ گراف" کو ذخیرہ کرنا ممکن ہے۔
لہذا، ہمارے پاس ایک غیر وزنی گراف ہے، جس کے ہر کنارے کے لیے اسے ذخیرہ کرنا ضروری ہے، مثال کے طور پر، 2 اضافی خصوصیات جو عدد کے ذریعہ بیان کی گئی ہیں۔ اس صورت میں، یہ ممکن ہے کہ اس کے ملحقہ ویکٹر کو "جوڑے" کے نہیں بلکہ عدد کے "چوکوارٹیٹس" کے ترتیب شدہ سیٹ کے طور پر بیان کیا جائے (a[2i]، a[2i+1]، a[2i+2]، a [2i+3]…)، جہاں a[2i+2] اور a[2i+3] متعلقہ کنارے کی خصوصیات کا تعین کریں گے۔ کناروں کے عدد کے وزن والے گراف کے لیے، ترتیب عام طور پر ایک جیسی ہوتی ہے (فرق صرف یہ ہوگا کہ اوصاف کنارے کے وزن کی پیروی کریں گے اور عناصر a[2i+3] اور a[2i+4] کے ذریعے بیان کیے جائیں گے۔ ، اور کنارے خود 4 نہیں بلکہ 5 ترتیب شدہ نمبروں کی وضاحت کی جائے گی)۔ اور غیر عددی کنارے کے وزن والے گراف کے لیے، خصوصیات کو اس کے غیر وزنی جزو میں لکھا جا سکتا ہے۔
عددی کنارے کے وزن کے ساتھ گرافس کے لیے ایک ایسوسی ایٹیو ملحقہ سرنی کا استعمال کرتے وقت، یہ ممکن ہے کہ ایک قدر کے طور پر کسی ایک عدد کو نہیں، بلکہ اعداد کی ایک سرنی (ویکٹر) کے طور پر متعین کیا جائے جو کہ کسی کنارے کے وزن کے علاوہ، اس کے دیگر تمام ضروری ہیں۔ خصوصیات. ایک ہی وقت میں، غیر عددی وزن کی صورت میں ایک تکلیف یہ ہوگی کہ فلوٹنگ پوائنٹ نمبر کے ساتھ ایک نشان کی وضاحت کرنے کی ضرورت ہوگی (ہاں، یہ ایک تکلیف ہے، لیکن اگر اس طرح کے بہت سے نشانات نہیں ہیں، اور اگر آپ نہیں کرتے ہیں) انہیں بہت "مشکل" ڈبل سیٹ نہ کریں، پھر یہ کچھ بھی نہیں ہوسکتا ہے)۔ اس کا مطلب یہ ہے کہ C++ میں، توسیعی ایسوسی ایٹیو ملحقہ صفوں کی وضاحت اس طرح کی جا سکتی ہے: std::map , std::vector> or std::map , std::vector، جس میں "key-value-vector" میں پہلی قدر کنارے کا وزن ہو گی، اور پھر اس کی صفات کے عددی عہدہ واقع ہوتے ہیں۔
ادب:
عام طور پر گراف اور الگورتھم کے بارے میں:
1. کورمین، تھامس ایچ، لیزرسن، چارلس آئی، ریویسٹ، رونالڈ ایل، سٹین، کلفورڈ۔ الگورتھم: تعمیر اور تجزیہ، دوسرا ایڈیشن: ٹرانس۔ انگریزی سے – ایم: ولیمز پبلشنگ ہاؤس، 2۔
2. ہراری فرینک۔ گراف تھیوری۔ م: میر، 1973۔
ان ہی ویکٹر اور ملحقہ صفوں کے بارے میں مصنف کی رپورٹ:
3. چرنوخوف S.A. گرافس کی نمائندگی اور ذخیرہ کرنے کے طریقوں کے طور پر ملحقہ ویکٹر اور ایسوسی ایٹیو ملحقہ سرنی / SA Chernouhov۔ ملحقہ ویکٹر اور ملحقہ نقشہ بطور ڈیٹا ڈھانچہ گراف کی نمائندگی کرنے کے لیے // بین الاقوامی سائنسی اور عملی کانفرنس کے مضامین کا مجموعہ "جدید پیشرفت کے نتائج کو لاگو کرنے کے مسائل اور ان کو حل کرنے کے طریقے" (سراتوف، 14.09.2019 ستمبر، 2019)۔ – سٹرلیٹامک: AMI، 65، صفحہ۔ 69-XNUMX
موضوع پر مفید آن لائن ذرائع:
4.
5.
ماخذ: www.habr.com