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

جز
ربات:اصلاح فاصلهٔ مجازی
جز (ربات: اصلاح ترکیبی)
جز (ربات:اصلاح فاصلهٔ مجازی)
'''درخت پوشای بهینه''' در [[گراف|گراف‌های]] ارزش دار (وزن دار) ساخته می‌شود.
 
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال هاییال‌های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گرف همبند وزن دار) درختی است که بین درخت هایدرخت‌های پوشای آن گراف، مجموع وزن یال هاییال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل می توان از الگوریتم هایالگوریتم‌های متفاوتی استفاده نمود.البته بطور کلی دو الگوریتم برای درخت پوشای مینیمم وجود دارد که عبارتند از :
[[الگوریتم کراسکال]]
[[الگوریتم پریم]]
{{پایان چپ چین}}
 
* ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت هادرخت‌ها یکسان است.
* مرتبهٔ زمانی الگوریتم پریم برابر (o(n^2 است. (حلقهٔ while، برای n دفعه و عمل یافتن از میان لبه‌های متصل به یک مجموعه دور خاص n دفعه اتفاق می افتد؛ که در مجموع برابر n^2 دفعه می‌شود).
 
از روش هایروش‌های دیگر برای یافتن درخت پوشای بهینه می‌توان الگوریتم هایالگوریتم‌های زیر را نام برد:
[[الگوریتم دایکسترا]]
[[الگوریتم سولین]]
 
== الگوریتم دایکسترا ==
این الگوریتم بصورت حریصانه عمل نموده و به‌دنبال یافتن کوتاه ترینکوتاه‌ترین مسیر ممکن بین یک نود و هر نود دلخواه دیگر، در یک گراف وزن دار و جهت دار می‌باشد. ورودی این الگوریتم همیشه یک ماتریس دو بعدی است که همان ماتریس وزن گراف است.
 
{{چپ چین}}
۲۵٬۵۹۴

ویرایش