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