گراف (ساختار داده): تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Rey dehghan (بحث | مشارکت‌ها) جزبدون خلاصۀ ویرایش |
Rey dehghan (بحث | مشارکت‌ها) اضافه کردن جدول |
||
خط ۱:
[[پرونده:گراف غیر بازه‌ای.jpg|جایگزین=گرافی با 5 راس و 7 یال|بندانگشتی|گرافی با 5 راس و 7 یال]]
در [[علوم رایانه]] یک '''گراف'''، داده‌ساختاری انتزاعی است که به صورت گراف [[گراف جهت‌دار|جهت دار]] و
یک '''[[داده ساختار]] گراف''' اساساً از یک مجموعهٔ متناهیِ [[زوج مرتب|زوج‌های مرتب]]
== عملیات ها ==
خط ۱۶:
* مقداردهی راس (''G'', ''x,v'') :مقدار مربوط به رأس x را v قرار می دهد؛
در [[گراف وزن‌دار|گراف وزن دار]]
* گرفتن ارزش یال (''G'', ''x,y''):مقدار مربوط به یال گذرنده از (x، y) را باز می گرداند؛
سطر ۲۴ ⟵ ۲۶:
ساختار داده های مختلفی برای نمایش گراف ها در عمل استفاده می شود :
راس ها به عنوان سوابق یا اشیا ذخیره می شوند و هر رأس لیستی از رأس های مجاور را ذخیره می کند. این ساختار داده ها اجازه ذخیره سازی داده های اضافی در رأس ها را می دهد. داده های اضافی را می توان ذخیره کرد اگر یال ها نیز به عنوان اشیا ذخیره شوند، در این صورت هر رأس یال های حادث بر خود را ذخیره می کند و هر یال رأس حاد خود را ذخیره می کند.
# '''[[ماتریس مجاورت]]'''.▼
# [[ماتریس وقوع|'''ماتریس وقوع''']]▼
یک ماتریس دو بعدی، که در آن ردیف ها نشان دهنده رأس مبدا و ستون ها نشان دهنده راس مقصد هستند. داده ها در یال ها و رأس ها باید در خارج از ماتریس ذخیره شوند. فقط هزینه یک یال می تواند بین هر جفت رأس ذخیره شود.
یک ماتریس بولی دو بعدی، که در آن ردیف ها نشان دهنده رأس ها و ستون هانشان دهنده یال ها هستند. ورودی ها نشان می دهند که آیا رأس یک ردیف به یال یک ستون متصل است یا خیر.
جدول زیر، هزینه [[پیچیدگی زمانی]] را برای انجام عملیات مختلف در گراف ها، برای هر یک از این نمایش ها، | V | نشان دهنده تعداد رأس ها و | E | تعداد لبه هاست .
{| class="wikitable"
|+
!
!لیست پیوندی
!ماتریس مجاورت
!ماتریس وقوع
|-
|ذخیره گراف
|<math>O(|V|+|E|)</math>
|<math>O(|V|^2)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|درج راس
|<math>O(1)</math>
|<math>O(|V|^2)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|درج یال
|<math>O(1)</math>
|<math>O(1)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|حذف راس
|<math>O(|E|)</math>
|<math>O(|V|^2)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|حذف یال
|<math>O(|V|)</math>
|<math>O(1)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|سوال: آیا رأس X و Y مجاور هستند؟
(فرض بر این است که موقعیت ذخیره سازی آنها شناخته شده است)
هر سه راه قابل اجرا برای [[گراف جهت دارِ|گراف‌های جهت‌دار]] و بدون جهت است. نمایش '''لیست مجاورت''' معمولاً ترجیح داده می‌شود چرا که یک روش فشرده برای نمایش [[گراف کم یال|گراف‌های کم یال]] فراهم می‌کند. اگر گراف [[گراف متراکم|متراکم]]▼
|<math>O(|V|)</math>
|<math>O(1)</math>
|<math>O(|E|)</math>
|}
▲هر سه راه قابل اجرا برای [[گراف
یا همان '''پر یال''' باشد، نمایشِ '''ماتریس مجاورت''' مقدم است. همچنین در مواقعی که نیاز داریم سریعاً بدانیم که آیا به ازای دو رأس داده شده
یال متصل‌کنندهٔ بینشان وجود دارد یا خیر، از لیست مجاورت استفاده می‌کنیم.
| |||