گراف (ساختار داده): تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Rey dehghan (بحث | مشارکت‌ها) جزبدون خلاصۀ ویرایش |
Rey dehghan (بحث | مشارکت‌ها) جزبدون خلاصۀ ویرایش |
||
خط ۷۳:
|<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" />.
== الگوریتم‌های گراف ==▼
الگوریتم‌های گراف زمینهٔ مهم علاقه در علوم رایانه به حساب می‌آیند. برخی از عملیاتِ مربوط به گراف‌ها عبارتند از: پیدا کردن مسیری بین دو گره، مانند [[جستجوی عمق اول]] و [[جستجوی سطح اول]] و پیدا کردن کوتاهترین مسیر از یک گره به دیگری، مانند [[الگوریتم دیکسترا]]. یک روش برای پیدا کردن کوتاهترین مسیر بین هر گره و تمام گره‌های دیگر هم وجود دارد به نام [[الگوریتم فلوید-وارشال]].▼
{{ساختمان داده‌ها}}▼
== همچنین ببینید ==
سطر ۹۷ ⟵ ۱۰۰:
* [[الگوریتم جستجوی عمق اول|جستجوی عمق اول]]
* [[الگوریتم جستجوی اول سطح|جستجوی سطح اول]]
▲== الگوریتم‌های گراف ==
▲الگوریتم‌های گراف زمینهٔ مهم علاقه در علوم رایانه به حساب می‌آیند. برخی از عملیاتِ مربوط به گراف‌ها عبارتند از: پیدا کردن مسیری بین دو گره، مانند [[جستجوی عمق اول]] و [[جستجوی سطح اول]] و پیدا کردن کوتاهترین مسیر از یک گره به دیگری، مانند [[الگوریتم دیکسترا]]. یک روش برای پیدا کردن کوتاهترین مسیر بین هر گره و تمام گره‌های دیگر هم وجود دارد به نام [[الگوریتم فلوید-وارشال]].
▲{{ساختمان داده‌ها}}
== منابع ==
| |||