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

جز
جز (ربات ردهٔ همسنگ (۲۲) +تمیز(۲.۷): + رده:درخت پوشا)
[[الگوریتم پریم]]
[[الگوریتم سولین]]
 
 
== الگوریتم کروسکال ==
پس اگرگرافی یالهای کمی داردبهتراست ازروش کروسکال واگریالهای زیادی دارد بهتراست ازروش پریم استفاده کنیم.
 
{{چپ‌چین}}
 
{{چپ چین}}
<source lang=cpp>
1 function Kruskal(G)
17 return tree T
</source>
{{پایان چپ چینچپ‌چین}}
 
نحوهٔ کار الگوریتم کراسکال به این صورت است که یک جنگل از درخت هارا به ترتیب با هم ادغام می‌کند تا به یک درخت واحد برسد. در اینجا نمونه‌ای از چگونگی عملکرد الگوریتم کراسکال آورده‌ایم:
== الگوریتم پریم ==
در این روش از یک رأس شروع می کنیم و کمترین یال (یال با کمترین وزن) که از آن می گذرد را انتخاب می کنیم. در مرحله بعد یالی انتخاب می‌شود که کمترین وزن را در بین یال‌هایی که از دو گره موجود می گذرد داشته باشیم. به همین ترتیب در مرحله بعد یالی انتخاب می‌گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می گذرد داشته باشد. این روال را آنقدر تکرار می کنیم تا درخت پوشای بهینه حاصل شود. باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می‌شود که در گراف دور ایجاد نکند. تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.
{{چپ چینچپ‌چین}}
<source lang=cpp>
while latest_addition = remove minimum in Q
add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)
for each adjacent of latest_addition
if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) < min_distance of adjacent)
set parent of adjacent to latest_addition
set min_distance of adjacent to weight-function(latest_addition, adjacent)
update adjacent in Q, order by min_distance
</source>
{{پایان چپ چینچپ‌چین}}
 
* ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت‌ها یکسان است.
* مرتبهٔ زمانی الگوریتم پریم برابر (o(n^2 است. (حلقهٔ while، برای n دفعه و عمل یافتن از میان لبه‌های متصل به یک مجموعه دور خاص n دفعه اتفاق می افتد؛ که در مجموع برابر n^2 دفعه می‌شود).
 
== منابع ==
{{پانویس}}
 
{{چپ چینچپ‌چین}}
* [http://en.wikipedia.org/wiki/Kruskal_algorithm]
* [http://en.wikipedia.org/wiki/Prim_algorithm]
* [http://www.jozve-computer.blogfa.com]
* [http://www.erfanrad.blogfa.com]
{{پایان چپ چینچپ‌چین}}
 
[[رده:درخت پوشا]]
[[رده:مسئله‌های با پیچیدگی زمانی چندجمله‌ای]]
[[رده:نظریه گراف]]
۹۸٬۹۰۸

ویرایش