الگوریتم کراسکال: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
←شبه کد الگوریتم کروسکال: ابرابزار |
جز ربات ردهٔ همسنگ (۲۲) +مرتب+تمیز(۲.۷): + رده:درخت پوشا |
||
خط ۱۷:
۳-در صورتی که مرحله ۲ دیگر قابل اجرا نیست توقف کن.
== مثال ==
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
سطر ۳۸ ⟵ ۳۷:
|در ادامه، کوتاهترین یال بعدی یعنی '''BE''' انتخاب میشود با طول 7.در این مرحله یالهای '''BC''' و '''DE''' و '''FE''' با رنگ قرمز نشان داده شده اند زیرا انتخاب هرکدام موجب ایجاد دور میشود.
|-
|[[
|سرانجام الگوریتم با انتخاب یال '''EG''' با طول 9 پایان میپذیرد و درخت پوشای کمینه ایجاد میشود.
سطر ۷۰ ⟵ ۶۹:
مسئله:یک درخت پوشای می نیمم مشخص کنید.
ورودی:عدد صحیح n>=2
خروجی:مجموعهای از لبهها 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]]
|