تفاوت میان نسخه‌های «درخت پوشای کمینه»

جز
ربات:افزودن الگو ناوباکس {{الگوریتم‌های بهینه‌سازی}}
جز (ربات:افزودن الگو ناوباکس {{الگوریتم‌های بهینه‌سازی}})
به چگونگی پیاده سازی صف اولویت Q بستگی دارد. اگر Q به صورت min-heap دودویی پیاده‌سازی شود. می‌توانیم از روال BUILD-MIN-HEAP در خطوط ۵-۱ برای [[مقدار دهی اولیه]] در زمان(O(V استفاده کنیم. بدنه حلقهwhile، |V| بار اجرا می‌شود. و چون هر عمل EXTRACT-MIN زمان(O(lgV را صرف می‌کند زمان کل برای همه فراخوانی EXTRA-MIN برابر(O(vlogV است. حلقه for در خطوط ۱۱-۸ روی هم رفته (O(E بار اجرا می‌شود چون مجموعه طول همه لیست‌های همجواری برابر ۲|E| می‌باشد. در داخل حلقه for بررسی برای عضویت در Q در خط ۹ می‌تواند در زمان ثابت با نگهداری یک بیت برای هر راس که بیان می‌کند آیا آن راس در Q قرار دارد یا خیر، پیاده سازی می‌شود و وقتی که راس از Q حذف شود بروز رسانی بیت انجام می‌گیرید. انتساب در خط۱۱ شامل یک عمل DECREASE- KEY ضمنی بر روی min-heap است که می‌تواند در min-heap دودویی در زمان(O(lgV پیاده‌سازی شود. بنابراین زمان کل برای الگوریتم Prim برابر(O(VlgV+ ElgV)= O(ElgV است که به طور مجانبی با پیاده‌سازی الگوریتم Kruskal یکسان می‌باشد.
اگر heap فیبوناچی برای پیاده سازی صف اولویت مینیمم Q استفاده شود. [[زمان اجرای الگوریتم]] Prim به(O(E+VlgV بهبود می‌یابد.
 
 
 
== الگوریتم سولین ==
* [http://www.erfanrad.blogfa.com]
{{پایان چپ‌چین}}
{{الگوریتم‌های بهینه‌سازی}}
 
[[رده:درخت پوشا]]
[[رده:مسئله‌های با پیچیدگی زمانی چندجمله‌ای]]
۵۷۷٬۴۵۰

ویرایش