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

هیچ تغییری در اندازه به وجود نیامده‌ است. ،  ۵ سال پیش
جز (ربات:افزودن الگو ناوباکس {{الگوریتم‌های بهینه‌سازی}})
برچسب: نیازمند بازبینی
در الگوریتم کراسکال یال‌های گراف را به ترتیب صعودی مرتب می کنیم. از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
 
این الگوزیتمالگوریتم نیزمشابه الگوریتم پریم برای یافتن درخت پوشای کمینه ی یک گراف به کارمی رود.دراین الگوریتم ابتدایال هاازکمترین وزن به بیشترین وزن مرتب می گردندسپس یال هابه ترتیب انتخاب شده واگریالی ایجادحلقه کندوکنارگذاشته می شود.عملیات هنگامی خاتمه می یابدکه تمام رأس هابه هم وصل شوندیااینکه تعدادیال های موجوددرF برابرn-1 شودکه n تعدادرأس ها است.که دربعضی کتابها بانام راشال مطرح شده است.شکل زیر مراحل کاررابرای یک گراف فرضی نشان می دهد.
 
بیشترزمان درالگوریتم کروسکال مربوط به مرتب سازی یالهاست.پس اگرتعدادیال e باشدزمان این الگوریتم ازمرتبه (e lg e) Ѳ خواهدبود.
کاربر ناشناس