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

جز
جایگزینی با اشتباه‌یاب: ابتدایال⟸ابتدا یال، ایجادحلقه⟸ایجاد حلقه، باشدیعنی⟸باشد یعنی، درالگوریتم⟸در الگوریتم، نسبتاپرباشدویالهای⟸نسبتا پر باشد و یالهای، نیزمشابه⟸نیز مشابه، هاازکمترین⟸ها از کمترین، واگریالی⟸و اگر یالی، کندوکنارگذاشته⟸کند و کنار گذاشته، گردندسپس⟸گردند سپس، یااینکه⟸یا اینکه، یابدکه⟸یابد که
جز (←‏زمان اجرای الگوریتم prim: اصلاح فاصله مجازی + اصلاح نویسه با ویرایشگر خودکار فارسی)
جز (جایگزینی با اشتباه‌یاب: ابتدایال⟸ابتدا یال، ایجادحلقه⟸ایجاد حلقه، باشدیعنی⟸باشد یعنی، درالگوریتم⟸در الگوریتم، نسبتاپرباشدویالهای⟸نسبتا پر باشد و یالهای، نیزمشابه⟸نیز مشابه، هاازکمترین⟸ها از کمترین، واگریالی⟸و اگر یالی، کندوکنارگذاشته⟸کند و کنار گذاشته، گردندسپس⟸گردند سپس، یااینکه⟸یا اینکه، یابدکه⟸یابد که)
در الگوریتم کراسکال یال‌های گراف را به ترتیب صعودی مرتب می کنیم. از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
 
این الگوریتم نیزمشابهنیز مشابه الگوریتم پریم برای یافتن درخت پوشای کمینهٔ یک گراف به کارمی رود.دراین الگوریتم ابتدایالابتدا هاازکمترینیال ها از کمترین وزن به بیشترین وزن مرتب می گردندسپسگردند سپس یال هابه ترتیب انتخاب شده واگریالیو ایجادحلقهاگر کندوکنارگذاشتهیالی ایجاد حلقه کند و کنار گذاشته می‌شود.عملیات هنگامی خاتمه می یابدکهیابد که تمام رأس هابه هم وصل شوند یااینکهیا اینکه تعداد یال‌های موجود در 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) Ѳ