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

جز
←‏الگوریتم پریم: می گذرد به می‌گذرد با استفاده از AWB
(←‏کاربرد درخت پوشای کمینه: اصلاح اشتباه تایپی)
برچسب‌ها: ویرایش با تلفن همراه ویرایش با مرورگر تلفن همراه
جز (←‏الگوریتم پریم: می گذرد به می‌گذرد با استفاده از AWB)
 
== الگوریتم پریم ==
در این روش از یک رأس شروع می کنیم و کمترین یال (یال با کمترین وزن) که از آن می گذردمی‌گذرد را انتخاب می کنیم. در مرحله بعد یالی انتخاب می‌شود که کمترین وزن را در بین یال‌هایی که از دو گره موجود می گذردمی‌گذرد داشته باشیم. به همین ترتیب در مرحله بعد یالی انتخاب می‌گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می گذردمی‌گذرد داشته باشد. این روال را آنقدر تکرار می کنیم تا درخت پوشای بهینه حاصل شود. باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می‌شود که در گراف دور ایجاد نکند. تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.
{{چپ‌چین}}
<source lang=cpp>