زمان کنونی: ۲۸ آذر ۱۳۹۷, ۱۰:۰۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

لیست مجاورتی

ارسال:
  

homa پرسیده:

لیست مجاورتی

اگر گراف G با لیست مجاورتی پیاده سازی بشود...پیچیدگی پیمایش BFS و DFS چه جوری بدست میاد؟؟
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین

۲
ارسال:
  

مازیار صفایی پاسخ داده:

RE: لیست مجاورتی

(۱۳ آذر ۱۳۹۰ ۰۸:۴۲ ب.ظ)homa نوشته شده توسط:  اگر گراف G با لیست مجاورتی پیاده سازی بشود...پیچیدگی پیمایش BFS و DFS چه جوری بدست میاد؟؟
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین

در کتاب CLRS تمام جزئیات رو ذکر کرده. البته این تحلیل بر اساس تحلیل سرشکن( تحلیل جمعی) می باشد.
در تحلیل جمعی اثبات شده که هزینه ورود به پشته و خروج O(1) است.
برای الگوریتم BFS ما در ابتدا کل گره‌ها را به رنگ سفید در می آوریم.
و در حلقه For این شرط رو قرار می دهیم که اگر گره سفید بود اجرا شود. در نتیجه هر گره فقط یک بار ملاقات می شود. از آن جا که برای نگهداری از یک صف استفاده می کنیم هر گروه فقط یک بار وارد صف می شود و یک بار از صف خارج می شود. در نتیجه با در نظر گرفته مرتبه زمانی O(1) و تعداد V نود اجرای این حلقه O(V) خواهد بود.
از اونجا که هر لیست دارای یالها می باشد و هر لیست فقط یک بار پیمایش می شود پس مرتبه زمانی این قسمت O(E) است. در حالبت کلی کل یالها در مجموع پیمایش می شود.

در نتیجه زمان اجرا برابر است با: O(V+E).

در مورد DFS هم به همین ترتیب.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  اشتراک لیست homa ۱۵ ۲,۷۹۱ ۲۴ بهمن ۱۳۹۰ ۱۲:۲۱ ق.ظ
آخرین ارسال: Maryam-X

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close