گراف (ساختار داده): تفاوت میان نسخه‌ها

در [[علوم رایانه]] یک '''گراف'''، داده‌ساختاری انتزاعی است که به صورت گراف [[گراف جهت‌دار|جهت دار]] و [[گراف (ریاضی)|بدون جهت]] پیاده سازی می‌شود و . هدفش به کارگیریِ مفهوم [[گراف]] از [[ریاضیات]] و به خصوص نظریه گراف است.

 

 

== عملیات ها ==

* مجاورت (''G'', ''x'', ''y''): امتحان اینکه آیا یک یال از رأس x به رأس y وجود دارد؛

* همسایه‌ها (''G'', ''x''):لیست تمام رأس‌ها را به طوری که یک یال از رأس x به رأس y وجود دارد؛

* گرفتن ارزش راس (''G'', ''x''): مقدار مربوط به رأس x را برمی گرداند؛

 

در [[گراف وزن‌دار|گراف وزن دار]] دستورات زیر نیز وجود دارد :

 

* گرفتن ارزش یال (''G'', ''x,y''):مقدار مربوط به یال گذرنده از (x، y) را باز می گرداند؛

 

== نمایش گراف‌ها ==

 

=== '''[[لیست مجاورت|لیست‌ مجاورت]]''' <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>