راشال و پریم

[mulanhary]

دوستان عزیز اگه تونستید این سوال رو جواب بدید:
درخت پوشایی که به روش پریم است بهینه تر است یا با روش راشال ؟

[raha_hakhamanesh]

با سلام خدمت دوستان
اگر اشتباه نکنم الگوریتم راشال همون کروسکال هست اگه اشتباه بود مقایسه زیر جواب شما نیست. بنابراین در اینجا من دو الگوریتم کروسکال و پریم رو مقایسه می کنم.
الگوریتم کروسکال در اکثر موارد دارای بهینه زمانی است اما توجه داشته باشید که همیشه اینطور نیست اما چه موقع زمان کروسکال از پریم بدتر می شود مربوط به تعداد نودهای گراف می شود یعنی اگر در حالتی که تعداد گره های گراف کم باشد زمان اجرایی کروسکال E logV خواهد بود در حالیکه پریم (V pow(2 می باشد اما اگر تعداد نودهای گراف زیاد شود به عبارتی V به سمت بینهایت میل کند زمان کروسکال برابر E pow(2) Log V می شود ولی پریم همواره همان مرتبه 2 خواهد بود .
جهت اطلاعات بیشتر به Algorithmics Theory and Practice نوشته Brassard مراجعه کنید .
موفق باشید .

[اَرژنگ]

دوستان عزیز اگه تونستید این سوال رو جواب بدید:
درخت پوشایی که به روش پریم است بهینه تر است یا با روش راشال ؟

بر طبقه http://www.cs.sunysb.edu/~algorith/l...od/node18.html
Floyd-Warshall
بهینه تره.

[mohandese_hiclass]

البته اگه از لحاظ بهینگی بحث کنیم یعنی از لحاظ ایجاد درخت پوشای مینیمال هر دو یکی هستن ولی از جهات دیگه پاسخ رها کامله