ویکی‌پدیا

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

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
Hamid Hassani (بحث | مشارکت‌ها)
۴۹٬۷۹۷ ویرایش‌ها
جز جایگزینی با اشتباه‌یاب: دستورات⟸دستورهای، سوال⟸سؤال، حدف⟸حذف
Hamid Hassani (بحث | مشارکت‌ها)
۴۹٬۷۹۷ ویرایش‌ها
جز ویرایش به‌وسیلهٔ ابرابزار:
خط ۱:
[[پرونده:گراف غیر بازه‌ای.jpg|جایگزین=گرافی با 5۵ راس و 7۷ یال|بندانگشتی|گرافی با 5۵ راس و 7۷ یال]]
در [[علوم رایانه]] یک '''گراف'''، داده‌ساختاری انتزاعی است که به صورت گراف [[گراف جهت‌دار|جهت دار]] و [[گراف (ریاضی)|بدون جهت]] پیاده‌سازی می‌شود و . هدفش به کارگیریِ مفهوم [[گراف]] از [[ریاضیات]] و به خصوص نظریه گراف است.
 
یک '''[[داده ساختار]] گراف''' اساساً از یک مجموعهٔ متناهیِ [[زوج مرتب|زوج‌های مرتب]] موسوم به '''یال''' شامل واحدهایی به نام '''رأس''' یا '''گره''' تشکیل می‌شود؛ همان‌طور که در ریاضیات به ازای یک یال (u,v) می‌گوییم که u به v می‌رود یا u و v مجاورند. همچنین می‌توان به هر یال یک گراف یک عدد نسبت داد که در این صورت [[گراف وزن‌دار|گراف وزن دار]] به وجود می آید می‌آید.
 
== عملیات ها ==
عملیات ابتدایی ارائه شده توسط یک ساختار داده گراف G معمولاً شامل <ref>{{Cite journal|last=Bowyer|first=A|date=2002-11|title=LEDA—a platform for combinatorial and geometric computing Kurt Mehlhorn and Stefan Näher, Cambridge University Press, Cambridge, UK, 1999, £50 ($80), 1018 pages, {{شابک|0-521-56329-1}}|url=http://dx.doi.org/10.1016/s0010-4485(01)00159-2|journal=Computer-Aided Design|volume=34|issue=13|pages=1047–1048|doi=10.1016/s0010-4485(01)00159-2|issn=0010-4485}}</ref>:▼
 
== عملیات‌ها ==
▲عملیات ابتدایی ارائه شده توسط یک ساختار داده گراف G معمولاً شامل :<ref>{{Cite journal|last=Bowyer|first=A|date=2002-11|title=LEDA—a platform for combinatorial and geometric computing Kurt Mehlhorn and Stefan Näher, Cambridge University Press, Cambridge, UK, 1999, £50 ($80), 1018 pages, {{شابک|0-521-56329-1}}|url=http://dx.doi.org/10.1016/s0010-4485(01)00159-2|journal=Computer-Aided Design|volume=34|issue=13|pages=1047–1048|doi=10.1016/s0010-4485(01)00159-2|issn=0010-4485}}</ref>:
* مجاورت (''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،x, y) را به v تنظیم می‌کند؛بازمی‌گرداند؛
▲* گرفتنمقدار ارزشدهی یال (''G'', ''x'', ''y'', ''v''): مقدار مربوط به یال گذرنده ازلبه (x،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=15811332941-58113-329-4}}</ref> ===
راس‌ها به عنوان سوابق یا اشیا ذخیره می‌شوند و هر رأس لیستی از رأس‌های مجاور را ذخیره می‌کند. این ساختار داده‌ها اجازه ذخیره‌سازی داده‌های اضافی در رأس‌ها را می‌دهد. داده‌های اضافی را می‌توان ذخیره کرد اگر یال‌ها نیز به عنوان اشیا ذخیره شوند، در این صورت هر رأس یال‌های حادث بر خود را ذخیره می‌کند و هر یال رأس حاد خود را ذخیره می‌کند.
 
سطر ۳۳ ⟵ ۳۱:
یک ماتریس بولی دو بعدی، که در آن ردیف‌ها نشان دهنده رأس‌ها و ستون هانشان دهنده یال‌ها هستند. ورودی‌ها نشان می‌دهند که آیا رأس یک ردیف به یال یک ستون متصل است یا خیر.
 
جدول زیر، هزینه [[پیچیدگی زمانی]] را برای انجام عملیات مختلف در گراف‌ها، برای هر یک از این نمایش‌ها، | V | نشان دهنده تعداد رأس‌ها و | E | تعداد لبه هاست .
{| class="wikitable"
|+
سطر ۶۱ ⟵ ۵۹:
|<math>O(|V|\cdot|E|)</math>
|-
|حذف یال
|<math>O(|V|)</math>
|<math>O(1)</math>
سطر ۷۳ ⟵ ۷۱:
|<math>O(|E|)</math>
|}
هر سه راه قابل اجرا برای [[گراف جهت‌دار|گراف‌گراف جهت دار]] و بدون جهت است. نمایش '''لیست مجاورت''' معمولاً ترجیح داده می‌شود چرا که یک روش فشرده برای نمایش [[گراف کم یال|گراف‌های کم یال]] فراهم می‌کند. اگر گراف [[گراف متراکم|متراکم]] یا همان '''پر یال''' باشد، نمایشِ '''ماتریس مجاورت''' مقدم است. همچنین در مواقعی که نیاز داریم سریعاً بدانیم که آیا به ازای دو رأس داده شده
یال متصل‌کنندهٔ بینشان وجود دارد یا خیر، از لیست مجاورت استفاده می‌کنیم.
طبقه‌بندی انواع دوگان [[گراف دوگان]] گراف‌هایی که تاکنون در علوم مختلف تعریف و استفاده شده‌اند، بر اساس نحوه استخراج به دو گروه بر مبنای گراف اولیه و مفهومی تقسیم‌بندی شده‌اند. در ادامه وجه تسمیه و مشخصات آن‌ها شرح داده شده‌اند.
سطر ۸۷ ⟵ ۸۵:
از دوگان ورونی گراف برای تقریب الگوریتم‌های کوتاه‌ترین مسی بر مبنای معیار فاصله استفاده کرده‌اند. چون تعداد گره‌ها در دوگان ورونی گراف به مراتب کمتر از گراف اولیه است، به همین دلیل آن‌ها نشان داده‌اند که جواب تقریبی مسئله کوتاه‌ترین مسیر بر مبنای فاصله را می‌توان در دوگان ورونی گراف اولیه محاسبه کرد.
 
Wallgrun <ref name=":0">{{یادکرد کتاب|نشانی=http://dx.doi.org/10.1007/978-3-642-10345-2_6|عنوان=Global Mapping: Minimal Route Graphs Under Spatial Constraints|نام خانوادگی=Wallgrün|نام=Jan Oliver|تاریخ=2009-11-10|ناشر=Springer Berlin Heidelberg|شابک=9783642103025|مکان=Berlin, Heidelberg|صفحات=113–146}}</ref> نشان داده‌است که از دوگان ورونی گراف می‌توان در مسائل طراحی حرکت رباتها استفاده برد. طراحی حرکت یک ربات در یک محدوده بسته باید بر اساس مشاهدات لحظه‌ای ربات انجام شود به نحوی که بدون برخورد با موانع و دیوارها با پیمودن کوتاه‌ترین مسیر به مقصد مورد نظر برسد. وی نشان داده‌است که ربات مورد نظر باید بر روی دوگان ورونی گراف مشاهداتش حرکت کند. وی همچنین چگونگی استخراج این دوگان ورونی گراف را بر اساس مشاهدات ربات بیان کرده‌است.<ref name=":0" />.
 
== الگوریتم‌های گراف ==
سطر ۹۳ ⟵ ۹۱:
{{ساختمان داده‌ها}}
 
== جستارهای وابسته ==
== همچنین ببینید ==
 
* [[پیمایش گراف]]
* [[پایگاه داده‌های گراف]]
برگرفته از «https://fa.wikipedia.org/wiki/گراف_(ساختار_داده)»