گراف ها (Graphs)
«گراف (Graph)» یک ساختار داده غیرخطی است. گراف از «رأس (Vertex/Node)» و «یال (Edge)» ساخته می شود. چون مسیرها متعددند، ترتیب خطی نداریم؛ بنابراین حرکت بین رأس ها آزادتر است.
تعریف ساده گراف
هر «رأس (Vertex)» همان نقطه/شیء است. هر «یال (Edge)» اتصال میان دو رأس است. چون چند مسیر داریم، گراف «غیرخطی» است. پس می توان از چند راه به مقصد رسید.
کاربردهای رایج گراف
- شبکه های اجتماعی؛ افراد رأس اند و رابطه ها یال اند.
- نقشه و مسیر؛ مکان ها رأس اند و جاده ها یال اند.
- اینترنت؛ صفحه ها رأس اند و لینک ها یال اند.
- زیست شناسی؛ شیوع بیماری یا شبکه عصبی با گراف مدل می شود.
نمایش گراف در حافظه
«نمایش (Representation)» یعنی شیوه ذخیره گراف. برخی نمایش ها فضا می کاهند. برخی جستجو را سریع تر می کنند. انتخاب نمایش به نوع گراف و کار ما بستگی دارد.
ماتریس مجاورت (Adjacency Matrix)
«ماتریس مجاورت» یک آرایه دوبعدی است. در خانه (i,j) اطلاعات یال از رأس i به j ذخیره می شود. در گراف بدون جهت، ماتریس متقارن است. برای وزن دار، به جای 1 وزن می نویسیم.
نکته: برای گراف های جهت دار، تقارن لازم نیست. کافی است مقدار درست را در جای درست بگذاریم.
لیست مجاورت (Adjacency List)
در «لیست مجاورت»، آرایه ای از رأس ها داریم. هر رأس به یک لیست پیوندی/آرایه از همسایه ها اشاره می کند. این روش برای گراف های «تنک (Sparse)» حافظه کمتری مصرف می کند.
نکته: در نسخه وزن دارِ جهت دار، هر ورودی می تواند جفتِ «شاخص همسایه، وزن» باشد.
گام های عملی ساده
- رأس ها را فهرست کن و برچسب بده.
- یال ها را مشخص کن؛ یک طرفه یا دوسویه.
- بین «ماتریس» و «لیست» انتخاب کن.
- برای وزن دار، وزن هر یال را درج کن.
پیوندها و مطالعه بیشتر
راهنمای کاملِ گراف ها همین صفحه است. همچنین برای ساختارهای مرتبط، به درخت های دودویی و AVL سر بزن.
منبع تصویری و توضیحات: W3Schools: Graphs. برای تعریف های رسمی تر: Wikipedia: Graph (ADT).
جمع بندی سریع
- گراف یعنی رأس ها و یال ها.
- غیرخطی است؛ مسیرها متعددند.
- ماتریس مجاورت ساده اما پُرحجم است.
- لیست مجاورت کم حجم برای گراف های تنک است.