گراف (Graph)
گراف: رأس و یال، انواع (جهت‌دار، وزن‌دار)، دو روش نمایش (ماتریس مجاورت و لیست همسایگی) و کاربردها
گراف چیست؟
گراف (Graph) مجموعه‌ای از رأس (Vertex) و یال (Edge) است که اتصالات را مدل می‌کند. برخلاف درخت، دور مجاز است و هر رأس می‌تواند به چندین رأس دیگر وصل باشد.
مثال‌ها: نقشه شهرها (رأس=شهر، یال=جاده)، شبکه اجتماعی (رأس=شخص، یال=دوستی)، اینترنت (رأس=سرور، یال=کابل).
انواع گراف
| نوع | ویژگی | مثال |
|---|---|---|
| بی‌جهت (Undirected) | یال دوطرفه است | دوستی فیسبوک |
| جهت‌دار (Directed) | یال یک‌طرفه است | فالو اینستاگرام |
| وزن‌دار (Weighted) | هر یال عدد/هزینه دارد | فاصله یا زمان جاده |
| وزن‌دار جهت‌دار | ترکیب هر دو | مسیریابی GPS |
نمایش ۱: ماتریس مجاورت
آرایه n×n؛ خانه [i][j] = ۱ اگر یال بین i و j باشد:
- ✓ بررسی وجود یال: O(1)
- ✗ حافظه O(n²) — برای گراف کم‌یال هدر زیاد
نمایش ۲: لیست همسایگی
برای هر رأس، لیست همسایه‌هایش (معمولاً با دیکشنری از لیست‌ها):
- ✓ حافظه O(V + E) — بهینه برای گراف کم‌یال
- ✗ بررسی وجود یال: O(درجه رأس)
کدام را انتخاب کنیم؟
| شرایط | انتخاب |
|---|---|
| گراف کم‌یال (Sparse) | لیست همسایگی ✓ |
| گراف پر یال (Dense) | ماتریس مجاورت |
| بررسی مکرر وجود یال | ماتریس ✓ |
| پیمایش BFS/DFS | لیست همسایگی ✓ |
در عمل، لیست همسایگی رایج‌تر است (اکثر گراف‌های واقعی کم‌یال‌اند).
مفاهیم مهم
- درجه (Degree): تعداد یال‌های یک رأس
- مسیر (Path): دنباله رأس‌های متصل
- دور (Cycle): مسیری که به نقطه شروع برمی‌گردد
- همبند (Connected): مسیری بین هر دو رأس وجود دارد
- گراف جهت‌دار بی‌دور (DAG): پایه ترتیب توپولوژیک و سیستم‌های وابستگی
نکته: درخت در واقع گراف همبند بی‌دور است! گراف تعمیم درخت است — هر درختی یک گراف است اما هر گرافی درخت نیست.
جمع‌بندی
- گراف = رأس + یال؛ مدل کردن روابط و شبکه‌ها
- انواع: جهت‌دار/بی‌جهت، وزن‌دار/بی‌وزن
- دو نمایش: ماتریس (بررسی سریع یال) و لیست همسایگی (حافظه بهینه)
- پیمایش‌ها (BFS/DFS) در بخش بعدی
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.