الگوریتم کراسکال: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده
YasBot (بحث | مشارکت‌ها)
جز ربات ردهٔ همسنگ (۲۲) +مرتب+تمیز(۲.۷): + رده:درخت پوشا
خط ۱۷:
۳-در صورتی که مرحله ۲ دیگر قابل اجرا نیست توقف کن.
 
== مثال ==
 
 
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
سطر ۳۸ ⟵ ۳۷:
|در ادامه، کوتاه‌ترین یال بعدی یعنی '''BE''' انتخاب می‌شود با طول 7.در این مرحله یال‌های '''BC''' و '''DE''' و '''FE''' با رنگ قرمز نشان داده شده اند زیرا انتخاب هرکدام موجب ایجاد دور می‌شود.
|-
|[[Imageپرونده:Kruskal Algorithm 6.svg|200px]]
|سرانجام الگوریتم با انتخاب یال '''EG''' با طول 9 پایان می‌پذیرد و درخت پوشای کمینه ایجاد می‌شود.
 
سطر ۷۰ ⟵ ۶۹:
مسئله:یک درخت پوشای می نیمم مشخص کنید.
 
ورودی:عدد صحیح n>=2 ,، عدد صحیح مثبت m و یک گراف بدون جهت و وزن دار و متصل شامل n گره و m لبه. گراف با یک مجموعه E که شامل لبه‌های گراف همراه با وزن‌های انها است نشان داده می‌شود
 
خروجی:مجموعه‌ای از لبه‌ها F در یک درخت پوشا مینیمم
 
{{چپچینچپ‌چین}}
<pre>
* Void kruskal (int n , int m ,
سطر ۹۸ ⟵ ۹۷:
* }
</pre>
{{پایان چپچینچپ‌چین}}
هرگاه n-1 لبه در F وجود داشته باشد,از حلقه whileخارج می‌شویم; زیرا در اینصورت , n-1 لبه در یک درخت پوشا وجود خواهد داشت
 
{{چپچینچپ‌چین}}
<pre>
void sort(struct krus ed[],int m)
سطر ۱۱۶ ⟵ ۱۱۵:
}
</pre>
{{پایان چپچینچپ‌چین}}
 
== منابع ==
{{پانویس}}
* نظریه گراف‌ها و کاربردهای آن، جی. ای. باندی و یو. اس. ار. مورتی. مترجم حمید ضرابی زاده، موسسه فرهنگی دیباگران تهران،.۱۳۷۸
* http://en.wikipedia.org/wiki/Kruskal_algorithm
 
[[رده:الگوریتم‌های گراف]]
[[رده:درخت پوشا]]
 
[[cs:Kruskalův algoritmus]]