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

 

{{چپ‌چین}}

1 function Kruskal(G)

2 for each vertex v in G do

16 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).

17 return tree T

{{پایان چپ‌چین}}

 

در این روش از یک رأس شروع می‌کنیم و کمترین یال (یال با کمترین وزن) که از آن می‌گذرد را انتخاب می‌کنیم. در مرحله بعد یالی انتخاب می‌شود که کمترین وزن را در بین یال‌هایی که از دو گره موجود می‌گذرد داشته باشیم. به همین ترتیب در مرحله بعد یالی انتخاب می‌گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می‌گذرد داشته باشد. این روال را آنقدر تکرار می‌کنیم تا درخت پوشای بهینه حاصل شود. باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می‌شود که در گراف دور ایجاد نکند. تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.

{{چپ‌چین}}

while latest_addition = remove minimum in Q

set is_in_Q of latest_addition to false

set min_distance of adjacent to weight-function(latest_addition, adjacent)

update adjacent in Q, order by min_distance

{{پایان چپ‌چین}}

* ممکن است درختهایی که الگوریتم مذکور تولید می‌کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همهٔ درخت‌ها یکسان است.