ساختارهای داده برای ذخیره سازی نمودارها: بررسی نمودارهای موجود و دو مورد "تقریبا جدید".

سلام بر همه

در این یادداشت، تصمیم گرفتم ساختارهای داده اصلی مورد استفاده برای ذخیره نمودارها در علوم کامپیوتر را فهرست کنم، و همچنین در مورد چند ساختار دیگر که به نوعی برای من "متبلور" شده اند صحبت خواهم کرد.

بنابراین، بیایید شروع کنیم. اما نه از همان ابتدا - من فکر می کنم همه ما از قبل می دانیم که یک گراف چیست و چیست (جهت دار، بدون جهت، وزن دار، بدون وزن، با یا بدون لبه ها و حلقه های متعدد).

پس بزن بریم. چه گزینه هایی برای ساختارهای داده برای "ذخیره سازی نمودار" داریم؟

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 لیست دنده ها. یک ساختار داده کاملاً محبوب. همانطور که Captain Obviousness به ما می گوید، لیست یال ها در واقع لیستی از یال های نمودار است که هر کدام با راس شروع، راس پایانی مشخص می شود (برای نمودارهای غیر جهت دار ترتیب در اینجا مهم نیست، اگرچه برای یکسان سازی می توانید از قوانین مختلفی استفاده کنید، به عنوان مثال، تعیین رئوس به ترتیب افزایش) و وزن (فقط برای نمودارهای وزنی).

می‌توانید به فهرست‌های ماتریسی فهرست‌شده در بالا با جزئیات بیشتری (و همراه با تصاویر) نگاه کنید، برای مثال، اینجا.

2.3 آرایه مجاورت. رایج ترین ساختار نیست. در هسته خود، شکلی از "بسته بندی" لیست های مجاورت در یک ساختار شمارش (آرایه، بردار) است. اولین n (با توجه به تعداد رئوس نمودار) عناصر چنین آرایه ای حاوی شاخص های شروع همان آرایه است که از آنجا شروع می شود که همه رئوس مجاور راس داده شده در یک ردیف نوشته می شوند.

در اینجا قابل درک ترین (برای خودم) توضیح را یافتم: ejuo.livejournal.com/4518.html

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] وزن این یال است. چنین نموداری همچنین می تواند جهت دار باشد یا نباشد.

حالت (ب): نمودار بدون وزن، وزن یال غیرصحیح

از آنجایی که برای مثال ذخیره عناصر ناهمگن در یک آرایه (بردار) غیرممکن است، پیاده سازی زیر امکان پذیر است. نمودار در یک جفت بردار ذخیره می شود که در آن بردار اول بردار مجاورت گراف بدون تعیین وزن است و بردار دوم حاوی وزن های مربوطه است (پیاده سازی ممکن برای 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> یا std::map ، std:: vector، که در آن اولین مقدار در "key-value-vector" وزن لبه خواهد بود و سپس تعیین عددی ویژگی های آن قرار می گیرد.

ادبیات:

در مورد نمودارها و الگوریتم ها به طور کلی:

1. کورمن، توماس اچ.، لیزرسون، چارلز آی.، ریوست، رونالد ال.، استین، کلیفورد. الگوریتم ها: ساخت و تحلیل، ویرایش دوم: ترانس. از انگلیسی - M.: انتشارات ویلیامز، 2.
2. هراری فرانک. نظریه گراف. م.: میر، 1973.
گزارش نویسنده در مورد همین آرایه برداری و انجمنی مجاورت ها:
3. Chernoukhov S.A. بردار مجاورت و آرایه مجاورت انجمنی به عنوان راه هایی برای نمایش و ذخیره نمودارها / SA Chernouhov. بردار مجاورت و نقشه مجاورت به عنوان ساختارهای داده برای نشان دادن نمودار // مجموعه مقالات کنفرانس علمی و عملی بین المللی "مشکلات اجرای نتایج پیشرفت های نوآورانه و راه های حل آنها" (ساراتوف، 14.09.2019 سپتامبر 2019). – Sterlitamak: AMI، 65، ص. 69-XNUMX
منابع آنلاین مفید در مورد موضوع:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

منبع: www.habr.com