گراف‌ها!

سلام. بعد از مدت کمی ناپیدایی، امرز به علل اجباری می‌خواهم در این پست گراف‌ها را توضیح بدهم!

اول از همه ببینیم این گراف یا به انگلیسی Graph که می‌گوید چیست؟

برای درک کردن گراف، کافی هست شکل زیر را به شما نشان دهم:

کاربرد

حالا که فهمیدیم گراف چیست، می‌خواهم کاربردهایش را بگوم.

گراف‌ها برای مدل کردن روابط و پردازش‌ها در بسیاری از مسائل علومی مانند فیزیک، زیست‌شناسی و حتی زندگی روزمره به کار می‌روند.

برای مثال شما می‌توانید کامپیوترهای متصل به یک شبکه را با گراف‌ها نمایش دهید.

کاربردهای بی‌انتهای گراف‌ها را می‌توانید از لینک زیر مشاهده کنید...

https://en.wikipedia.org/wiki/Graph_theory#Applications

(لینک بالا به علت مشکل ویرگول هست، مشکل اصلا از من نیست!)

گراف‌ها

در این بخش از متن، قرار هست کمی راجع به گراف‌ها یاد بگیریم!

در گراف‌ها ما دارای vertex (گاها point یا node) هستیم که معمولا vertices (جمع) نوشته می‌شوند!

این نودها در عکس بالا به شکل یک دایره‌ی سفید که وسط آن‌ها یک عدد هست وجود دارند.

علاوه بر vertices، گراف‌ها دارای edge هم هستند که با نام‌های link, line, arc هم شناخته می‌شوند.

الان باید راجع به یک چیز دیگر با هم حرف بزنیم تا بتوانم یکی از نکات مهم درباره‌ی edgeهای گراف را بگوم:

جهت‌دار با بی‌جهت

گراف‌ها را می‌توان در دو دسته‌ی directed یا جهت دار و بی‌جهت یا undirected تقسیم کرد.

گرافی که در بالا دیدید بی‌جهت یا undirected هست زیرا یال (6,4) با یال (4,6) برابر هست.

اما اگر به گراف شماره‌ی b نگاه کنید، متوجه خواهید شد که این رابطه یک‌طرفه و جهت دار هست، بنابراین گراف b یک گراف directed هست!

نکته‌ی مهم راجع به edgeها این بود که:

در یک گراف جهت‌دار، (a,b) برابر با (b,a) نیست در حالی که در یک گراف بی‌جهت، (a,b) و (b,a) با هم برابرند.

دو راه عمده برای پیاده‌سازی گراف‌ها هست:

• لیست‌های مجاور (adjacency list)
• ماتریس‌های مجاور (adjacency matrix)

البته، مطمئنا می‌توان با روش‌های دیگر هم گراف‌ها را پیاده‌سازی کرد. و روش پیاده‌سازی بستگی به عملیات‌هایی که می‌خواهید روی گراف انجام بدهید دارد.

در این پست فقط راه‌حل ماتریکس مجاور را بررسی می‌کنیم. (به علت سادگی بالا!)

ماتریکس مجاور

(ببخشید که تخت الفظی هست)

در این روش ما یک آرایه دو بُعدی با سایز V x V داریم که V برابر با تعداد راس‌های گراف هست.

در این روش ما اطلاعات را در یک آرایه می‌گذاریم که arr[i][j] نشان می‌دهد این گراف، دارای یک edge ازش i به j هست که دارای value یا weightای برابر با مقداری که در مکان arr[i][j] قرار دارد.

شما نمی‌توانید با این روش، گراف‌های جهت‌دار را پیاده‌سازی کنید!

مزایا

• این روش برای پیاده‌سازی راحت هست
• برداشتن یک edge فقط O(1) زمان می‌برد.

معایت

• حتی اگر تمام vertexها خالی باشند، باز هم V^2 تا حافظه اشغال می‌کند!
• اضافه کردن یک یال نیاز به O(V^2) زمان دارد.

پیاده‌سازی

برای دیدن پیاده‌سازی، این لینک را توصیه می‌کنم. با پایتون.

دوره آموزشی های تصویری ما را هم در یوتیوب دنبال کنید و حتما پیشنهاد میکنم پیج اینستاگرام تمشک رو دنبال کنید ، برای دسترسی به بعضی از کدهای آموزش ها هم به گیتهاب تمشک سر بزنید.

اگر بازم از این آموزشها دوست داشتید یادتون نره دنبال کردن انتشارات ما رو ?.

© منبع : تمشک، geeksforgeeks.org