۰
subtitle
ارسال: #۱
  
لیست مجاورتی
اگر گراف G با لیست مجاورتی پیاده سازی بشود...پیچیدگی پیمایش BFS و DFS چه جوری بدست میاد؟؟
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین
۲
ارسال: #۲
  
RE: لیست مجاورتی
(۱۳ آذر ۱۳۹۰ ۰۸:۴۲ ب.ظ)homa نوشته شده توسط: اگر گراف G با لیست مجاورتی پیاده سازی بشود...پیچیدگی پیمایش BFS و DFS چه جوری بدست میاد؟؟
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین
در کتاب CLRS تمام جزئیات رو ذکر کرده. البته این تحلیل بر اساس تحلیل سرشکن( تحلیل جمعی) می باشد.
در تحلیل جمعی اثبات شده که هزینه ورود به پشته و خروج O(1) است.
برای الگوریتم BFS ما در ابتدا کل گرهها را به رنگ سفید در می آوریم.
و در حلقه For این شرط رو قرار می دهیم که اگر گره سفید بود اجرا شود. در نتیجه هر گره فقط یک بار ملاقات می شود. از آن جا که برای نگهداری از یک صف استفاده می کنیم هر گروه فقط یک بار وارد صف می شود و یک بار از صف خارج می شود. در نتیجه با در نظر گرفته مرتبه زمانی O(1) و تعداد V نود اجرای این حلقه O(V) خواهد بود.
از اونجا که هر لیست دارای یالها می باشد و هر لیست فقط یک بار پیمایش می شود پس مرتبه زمانی این قسمت O(E) است. در حالبت کلی کل یالها در مجموع پیمایش می شود.
در نتیجه زمان اجرا برابر است با: O(V+E).
در مورد DFS هم به همین ترتیب.
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
لیست مجاورتی ؟؟؟ | jafarir | ۲ | ۱,۹۷۰ |
۲۵ آذر ۱۳۹۱ ۰۹:۴۲ ق.ظ آخرین ارسال: jafarir |
|
اشتراک لیست | homa | ۱۵ | ۹,۲۶۹ |
۲۴ بهمن ۱۳۹۰ ۱۲:۲۱ ق.ظ آخرین ارسال: Maryam-X |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close