سڀني کي سلام.
هن نوٽ ۾، مون ڪمپيوٽر سائنس ۾ گرافس کي محفوظ ڪرڻ لاءِ استعمال ٿيندڙ مکيه ڊيٽا ڍانچين کي لسٽ ڪرڻ جو فيصلو ڪيو، ۽ مان ڪجهه وڌيڪ اهڙين اڏاوتن بابت به ڳالهائيندس، جيڪي ڪنهن نه ڪنهن طرح مون لاءِ ”ڪرسٽل ٿيل“ آهن.
سو، اچو ته شروع ڪريون. پر شروعات کان ئي نه - مان سمجهان ٿو ته اسان سڀ اڳ ۾ ئي ڄاڻون ٿا ته گراف ڇا آهي ۽ اهي ڇا آهن (هدايت، اڻ سڌي، وزن، اڻ وزن، گهڻن ڪنڊن ۽ لوپس سان يا بغير).
سو، اچو ته هلون. اسان وٽ "گراف اسٽوريج" لاءِ ڊيٽا جي جوڙجڪ لاءِ ڪهڙا اختيار آهن؟
1. ميٽرڪس ڊيٽا جي جوڙجڪ
1.1 ملائيندڙ ميٽرڪس. ويجهڙائي واري ميٽرڪس هڪ ميٽرڪس آهي جتي قطار ۽ ڪالمن جي هيڊنگنگ گراف جي عمودي انگن اکرن سان ملن ٿا، ۽ ان جي هر عنصر جي قيمت a(i,j) جي وچ ۾ ڪنڊن جي موجودگي يا غير موجودگي سان طئي ڪيو ويندو آهي. 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]،...، جتي مون کي 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] هن کنڊ جو وزن آهي. اهڙو گراف به هدايت ڪري سگهجي ٿو يا نه.
ڪيس (ب): اڻ وزني گراف، غير انٽيجر ايج وزن
جيئن ته هڪ صف (ویکٹر) ۾ متضاد عناصر کي ذخيرو ڪرڻ ناممڪن آهي، مثال طور، هيٺين عمل درآمد ممڪن آهي. گراف ویکٹر جي هڪ جوڙي ۾ محفوظ ڪيو ويو آهي، جنهن ۾ پهريون ویکٹر گراف جي ويجهڙائي وارو ویکٹر هوندو آهي بغير وزن جي وضاحت ڪرڻ، ۽ ٻئي ویکٹر ۾ لاڳاپيل وزن شامل آهن (سي ++: std::pair لاءِ ممڪن عمل ). اهڙيءَ طرح، پهرين ویکٹر جي انڊيڪس 2i، 2i+1 جي هيٺان عمودي جي هڪ جوڙي سان بيان ڪيل هڪ ڪنڊ لاءِ، وزن ٻئي ویکٹر جي انڊيڪس i هيٺان عنصر جي برابر هوندو.
خير، اهو ڇو ضروري آهي؟
خير، انهن لائينن جي ليکڪ کي اهو ڪافي مفيد مليو ته ڪيترن ئي مسئلن کي حل ڪرڻ لاء. خير، رسمي نقطي نظر کان، هيٺيان فائدا هوندا:
- ملندڙ ویکٹر، ڪنهن ٻئي ”شماري“ ڍانچي وانگر، ڪافي ٺهڪندڙ آهي، ويجهڙائي واري ميٽرڪس (اسپارس گرافس لاءِ) جي ڀيٽ ۾ گهٽ ميموري وٺندو آهي، ۽ ان تي عمل ڪرڻ نسبتاً آسان آهي.
- گراف جي عمدي، اصول ۾، به منفي انگن سان نشان لڳل ڪري سگهجي ٿو. ڇا جيڪڏهن اهڙي "تبديل" جي ضرورت آهي؟
- گراف مختلف وزنن (مثبت، منفي، حتي صفر) سان، گھڻن ڪنڊن ۽ گھڻن لوپس تي مشتمل ٿي سگھي ٿو. هتي ڪي به پابنديون نه آهن.
- توھان ڪنارن کي مختلف ملڪيتون پڻ تفويض ڪري سگھو ٿا - پر ان تي وڌيڪ لاءِ، سيڪشن 4 ڏسو.
بهرحال، اهو تسليم ڪيو وڃي ٿو ته هي "فهرست" کنڊ تائين جلدي رسائي جو مطلب ناهي. ۽ هتي Associative Adjacency Array اچي ٿو بچاءُ لاءِ، جنهن تي بحث هيٺ ڪيو ويو آهي.
3.2 ايسوسيئيٽيو ويجهڙائي واري صف
تنهن ڪري، جيڪڏهن ڪنهن مخصوص ڪنڊ تائين پهچ، ان جو وزن ۽ ٻيون خاصيتون اسان لاءِ نازڪ آهن، ۽ ياداشت جون گهرجون اسان کي ويجهڙائيءَ واري ميٽرڪس کي استعمال ڪرڻ جي اجازت نه ٿيون ڏين، ته پوءِ اچو ته ان مسئلي کي حل ڪرڻ لاءِ ڀرسان ويڪر کي ڪيئن بدلائي سگهون. تنهن ڪري، ڪنجي گراف جي هڪ ڪنڊ آهي، جنهن کي مقرر ڪري سگهجي ٿو هڪ ترتيب ڏنل عددن جي جوڙي جي طور تي. هي ڇا ٿو لڳي؟ ڇا اهو هڪ اتحادي صف ۾ هڪ اهم ناهي؟ ۽، جيڪڏهن ائين آهي، ته اسان ان تي عمل ڇو نٿا ڪريون؟ اچو ته اسان کي هڪ ايسوسيئيٽ ايري هجي جتي هر ڪيئي - هڪ ترتيب ڏنل عددن جو جوڙو - هڪ قدر سان لاڳاپيل هوندو - هڪ عدد يا حقيقي انگ جيڪو ڪنارن جي وزن کي بيان ڪري ٿو. C++ ۾، اهو مشورو ڏنو ويندو آهي ته هن ڍانچي کي std::map ڪنٽينر (std::map) جي بنياد تي لاڳو ڪيو وڃي int> or 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. ڪورمين، ٿامس ايڇ، ليزرسن، چارلس آءِ، ريويسٽ، رونالڊ ايل، اسٽين، ڪلفورڊ. Algorithms: تعمير ۽ تجزيو، 2nd ايڊيشن: ٽرانس. انگريزيءَ مان - ايم.: وليمس پبلشنگ هائوس، 2011.
2. هاري فرينڪ. گراف جو نظريو. م.: مير، 1973ع.
مصنف جي رپورٽ انهن ساڳين ویکٹر ۽ ملندڙ جڳهن بابت آهي:
3. چرنوخوف S.A. ملندڙ ویکٹر ۽ ايسوسيئيٽيو ملحقه صف جيئن ظاھر ڪرڻ ۽ گرافس کي ذخيرو ڪرڻ جا طريقا / SA Chernouhov. ويڪر ۽ ويجهڙائيءَ جو نقشو ڊيٽا جي جوڙجڪ جي طور تي گراف جي نمائندگي ڪرڻ لاءِ // بين الاقوامي سائنسي ۽ عملي ڪانفرنس جي آرٽيڪلز جو مجموعو ”جديد ترقيات جي نتيجن کي لاڳو ڪرڻ جا مسئلا ۽ انهن کي حل ڪرڻ جا طريقا“ (سراتوف، سيپٽمبر 14.09.2019، 2019). - Sterlitamak: AMI، 65، ص. 69-XNUMX
موضوع تي مفيد آن لائين ذريعن:
4.
5.
جو ذريعو: www.habr.com