الگوریتم کراسکال: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Azita araghi (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
Azita araghi (بحث | مشارکت‌ها) برچسب: افزودن فضای خالی زیاد(AF) |
||
خط ۶۵:
که این با <math>T</math> انتخاب در تناقض است. بنابرین <math>T=U</math> و در نتیجه<math> U</math> یک درخت بهینه‌است.
==شبه کد الگوریتم کروسکال==
{{چپچین}}▼
Void kruskal ( int n , int m ,▼
مسئله:یک درخت پوشای می نیمم مشخص کنید.
set _of_edges E,▼
ورودی:عدد صحیح n>=2 , عدد صحیح مثبت m و یک گراف بدون جهت و وزن دار و متصل شامل n گره و m لبه . گراف با یک مجموعه E که شامل لبه های گراف همراه با وزن های انها است نشان داده می شود
set_of_edges & F)▼
index i, j;▼
Set_pointer p , q ;▼
edge e;▼
Sort the m edges in E by weight in nondecreasing order ;▼
F=∅; ▼
While(number of edges in F is less than n-1){▼
e= edge with least weight not yet considered;▼
i, j = indices of vertices connected by e ;▼
p=find(i);▼
q=find(j);▼
if(!equal(p,q)){▼
merge(p,q);▼
add e to F ;▼
خروجی:مجموعه ای از لبه ها F در یک درخت پوشا مینیمم
▲{{چپچین}}
<pre>
▲* Void kruskal ( int n , int m ,
▲* set _of_edges E,
▲* set_of_edges & F)
* {
▲* index i, j;
▲* Set_pointer p , q ;
▲* edge e;
▲* Sort the m edges in E by weight in nondecreasing order ;
▲* F=∅;
* initial(n); //زیر مجموعه غیر الحاقی n مقدار دهی
▲* While(number of edges in F is less than n-1){
▲* e= edge with least weight not yet considered;
▲* i, j = indices of vertices connected by e ;
▲* p=find(i);
▲* q=find(j);
▲* if(!equal(p,q)){
▲* merge(p,q);
▲* add e to F ;
* }
* }
* }
== منابع ==
| |||