سلام
بچه ها کسی مراحل این الگوریتمو میتونه توضیح بده؟ یا لینکی چیزی؟
ساختمان پوران خیلی بد گفته و خیلی توش ابهام هست-مثلا اگر تو کنکور سوال بدن که در فلان مرحله کدوم یال اضافه میشه یا از این قبیل سوالات مشکل دارم
خب توی این الگوریتم توی مرحله اول برای هر گره یه یال با حداقل هزینه رو انتخاب میکنیم
بعد یه جنگل ایجاد میشه که برای اتصال جنگل ها هم یه یال با حداقل هزینه رو انتخاب میکنیم . همین !
فقط یادمون باشه که حلقه نباید ایجاد شه !
تعداد یالهایی هم که رسم میکنیم در آخر n-1 باید باشه
(۱۱ دى ۱۳۹۲ ۰۴:۳۳ ق.ظ)pooyaa نوشته شده توسط: سلام
بچه ها کسی مراحل این الگوریتمو میتونه توضیح بده؟ یا لینکی چیزی؟
ساختمان پوران خیلی بد گفته و خیلی توش ابهام هست-مثلا اگر تو کنکور سوال بدن که در فلان مرحله کدوم یال اضافه میشه یا از این قبیل سوالات مشکل دارم
سلام
در مرحله اول ما یه جنگل داریم یعنی باید یالهایی رو تو مرحله اول انتخاب کنید که کل رئوس رو شامل بشن و از مرحله بعد باید ب عدم تشکیل دور تو انتخاب یالها دقت کنید
مثال کتاب رو برا خودتون امتحان کنید
دقت کنید در مرحله اول یالهایی انتخاب میشن ک تمام رئوس رو در بر بگیرن
موفق باشید
پیچیدگی زمانیش چقدره؟
O(nlogn)
Sent from my SM-T210R using Tapatalk