گراف (ساختار داده): تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
FreshmanBot (بحث | مشارکتها) جز اصلاح فاصله مجازی + اصلاح نویسه، replaced: ها ← ها (17)، های ← های (5)، می تواند ← میتواند با ویرایشگر خودکار فارسی |
FreshmanBot (بحث | مشارکتها) جز اصلاح فاصله مجازی + اصلاح نویسه با ویرایشگر خودکار فارسی |
||
خط ۲:
در [[علوم رایانه]] یک '''گراف'''، دادهساختاری انتزاعی است که به صورت گراف [[گراف جهتدار|جهت دار]] و [[گراف (ریاضی)|بدون جهت]] پیاده سازی میشود و . هدفش به کارگیریِ مفهوم [[گراف]] از [[ریاضیات]] و به خصوص نظریه گراف است.
یک '''[[داده ساختار]] گراف''' اساساً از یک مجموعهٔ متناهیِ [[زوج مرتب|زوجهای مرتب]] موسوم به '''یال''' شامل واحدهایی به نام '''رأس''' یا '''گره''' تشکیل میشود؛ همانطور که در ریاضیات به ازای یک یال (u,v) میگوییم که u به v میرود یا u و v مجاورند. همچنین
== عملیات ها ==
خط ۹:
* مجاورت (''G'', ''x'', ''y''): امتحان اینکه آیا یک یال از رأس x به رأس y وجود دارد؛
* همسایهها (''G'', ''x''):لیست تمام رأسها را به طوری که یک یال از رأس x به رأس y وجود دارد؛
* درج راس(''G'', ''x'') :راس x را در صورت عدم وجود اضافه
* حدف راس (''G'', ''x'') :راس x را در صورت وجود حذف
* درج یال (''G'', ''x'', ''y''): یک یال از رأس x به رأس y اضافه
* حذف یال (''G'', ''x'', ''y''): یال از رأس x به رأس y را در صورت وجود حذف
* گرفتن ارزش راس (''G'', ''x''): مقدار مربوط به رأس x را برمی گرداند؛
* مقداردهی راس (''G'', ''x,v'') :مقدار مربوط به رأس x را v قرار
در [[گراف وزندار|گراف وزن دار]] دستورات زیر نیز وجود دارد :
* گرفتن ارزش یال (''G'', ''x,y''):مقدار مربوط به یال گذرنده از (x، y) را باز می گرداند؛
* مقدار دهی یال (''G'', ''x'', ''y'', ''v''): مقدار مربوط به لبه (x، y) را به v تنظیم
== نمایش گرافها ==
ساختار دادههای مختلفی برای نمایش گرافها در عمل استفاده
=== '''[[لیست مجاورت|لیست مجاورت]]''' <ref>{{Cite journal|last=Goodrich|first=Michael T.|last2=Tamassia|first2=Roberto|date=2001|title=Teaching internet algorithmics|url=http://dx.doi.org/10.1145/364447.364561|journal=Proceedings of the thirty-second SIGCSE technical symposium on Computer Science Education - SIGCSE '01|location=New York, New York, USA|publisher=ACM Press|doi=10.1145/364447.364561|isbn=1581133294}}</ref> ===
راسها به عنوان سوابق یا اشیا ذخیره
=== '''[[ماتریس مجاورت]]''' ===
خط ۶۸:
|سوال: آیا رأس X و Y مجاور هستند؟
(فرض بر این است که موقعیت
|<math>O(|V|)</math>
|<math>O(1)</math>
|