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

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