اگر گراف G با لیست مجاورتی پیاده سازی بشود...پیچیدگی پیمایش BFS و DFS چه جوری بدست میاد؟؟
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین
(۱۳ آذر ۱۳۹۰ ۰۸:۴۲ ب.ظ)homa نوشته شده توسط: اگر گراف G با لیست مجاورتی پیاده سازی بشود...پیچیدگی پیمایش BFS و DFS چه جوری بدست میاد؟؟
میدونم چه مقدار میشه...اما دلیل اینکه چرا اینجوریه رو نمی دونم...
ممنون اگه توضیح بدین
در کتاب CLRS تمام جزئیات رو ذکر کرده. البته این تحلیل بر اساس تحلیل سرشکن( تحلیل جمعی) می باشد.
در تحلیل جمعی اثبات شده که هزینه ورود به پشته و خروج O(1) است.
برای الگوریتم BFS ما در ابتدا کل گره‌ها را به رنگ سفید در می آوریم.
و در حلقه For این شرط رو قرار می دهیم که اگر گره سفید بود اجرا شود. در نتیجه هر گره فقط یک بار ملاقات می شود. از آن جا که برای نگهداری از یک صف استفاده می کنیم هر گروه فقط یک بار وارد صف می شود و یک بار از صف خارج می شود. در نتیجه با در نظر گرفته مرتبه زمانی O(1) و تعداد V نود اجرای این حلقه O(V) خواهد بود.
از اونجا که هر لیست دارای یالها می باشد و هر لیست فقط یک بار پیمایش می شود پس مرتبه زمانی این قسمت O(E) است. در حالبت کلی کل یالها در مجموع پیمایش می شود.
در نتیجه زمان اجرا برابر است با: O(V+E).
در مورد DFS هم به همین ترتیب.