ټولو ته سلام.
په دې یادښت کې، ما پریکړه وکړه چې د کمپیوټر ساینس کې د ګرافونو ذخیره کولو لپاره کارول شوي اصلي ډیټا جوړښتونه لیست کړم، او زه به د یو څو نورو داسې جوړښتونو په اړه هم وغږیږم چې یو څه زما لپاره "کرسټال شوی".
نو، راځئ چې پیل وکړو. مګر له پیل څخه نه - زه فکر کوم چې موږ ټول دمخه پوهیږو چې ګراف څه شی دی او هغه څه دي (لارښوونه شوي، غیر مستقیم، وزن شوي، بې وزنه، د څو څنډو او لوپونو سره یا پرته).
نو، راځئ چې لاړ شو. موږ د "ګراف ذخیره کولو" لپاره د ډیټا جوړښتونو لپاره کوم اختیارونه لرو؟
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]، ...، چیرې چې زه د c 0 شمیرل کیږي)، چیرې چې د شمیرو هر یو "درې پلټ" a[3i]، a[3i+1]، a[3i+2] د ګراف یوه څنډه مشخصوي د عمودی شمیره a[3i] ترمنځ او a[3i+1]، په ترتیب سره، او ارزښت a [3i+2] د دې څنډې وزن دی. دا ډول ګراف هم یا هم لارښود کیدی شي یا نه.
قضیه (ب): بې وزنه ګراف، غیر انټیجر څنډه وزن
څرنګه چې په یوه صف (ویکٹر) کې د متضاد عناصرو ذخیره کول ناممکن دي، د بیلګې په توګه، لاندې پلي کول ممکن دي. ګراف د ویکتورونو په جوړه کې زیرمه شوی، په کوم کې چې لومړی ویکتور د ګراف سره نږدې ویکتور دی پرته له دې چې وزنونه مشخص کړي، او دویم ویکتور ورته وزن لري (د 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. هراري فرانک. د ګراف تیوري. م.: میر، ۱۹۷۳.
لیکوال د همدې ویکتور او د ملحقاتو د تنظیمي لړۍ په اړه راپور ورکوي:
3. چرنوخوف S.A. د ګرافونو د نمایندګۍ او ذخیره کولو د لارو په توګه د ملحقه ویکتور او ملګري ملحقه صفونه / SA Chernouhov. د ګراف د نمایندګۍ لپاره د ډیټا جوړښتونو په توګه د نږدې والی ویکتور او نږدې نقشه // د نړیوال ساینسي او عملي کنفرانس د مقالو راټولول "د نوښت پرمختګونو پایلو پلي کولو ستونزې او د حل لارې چارې" (سراتوف، سپتمبر 14.09.2019، 2019). – سټرلیتامک: AMI، 65، مخ. 69-XNUMX
د موضوع په اړه ګټورې آنلاین سرچینې:
4.
5.
سرچینه: www.habr.com