الگوریتم کراسکال

1. یال پیوندی${\displaystyle e_1}$
   را طوری انتخاب کن که وزن آن کوچکترین مقدار موجود باشد.
2. اگر یال‌های ${\displaystyle e_i,...e_2,e_1}$
   انتخاب شده‌اند یال${\displaystyle e_{i+1}}$
   را از میان${\displaystyle E-\{e1,e_2,...,e_i\}}$
   به گونه‌ای انتخاب کن که:
   • زیرگراف با یال‌های ${\displaystyle e_1,e_2,...,e_{i+1}}$
     بدون دور باشد.
   • از میان یال‌های مشمول شرط (الف) وزن ${\displaystyle e_{i+1}}$
     دارای کمترین مقدار ممکن باشد.
3. در صورتی که مرحله ۲ دیگر قابل اجرا نیست توقف کن.

نمونه‌ای از خروجی برنامه:

ثابت می‌کنیم هر درخت فراگیر ${\displaystyle U}$

از طریق تناقض: به ازای هر درخت فراگیر ${\displaystyle T}$

${\displaystyle w(T^{{}^{\prime }})=w(T)+w(e_k)-w({e^{{}^{\prime }}}_k)}$

ولی در الگوریتم کراسکال ${\displaystyle e_k}$

${\displaystyle w({e^{{}^{\prime }}}_k)}$

پس

${\displaystyle w(T^{{}^{\prime }})}$

پس ${\displaystyle T^{{}^{\prime }}}$

${\displaystyle f(T^{{}^{\prime }})>k=f(T)}$

که این با ${\displaystyle T}$

مسئله:یک درخت پوشای می نیمم مشخص کنید.

ورودی:عدد صحیح n>=۲، عدد صحیح مثبت m و یک گراف بدون جهت و وزن دار و متصل شامل n گره و m یال. گراف با یک مجموعه E که شامل یال‌های گراف همراه با وزن‌های آن‌ها است نشان داده می‌شود

خروجی:مجموعه‌ای از یال‌ها F در یک درخت پوشا مینیمم

* 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 ;
* }
* }
* }

هرگاه n-1 یال در F وجود داشته باشد، از حلقه whileخارج می‌شویم؛ زیرا در اینصورت، n-1 یال در یک درخت پوشا وجود خواهد داشت

void sort(struct krus ed[],int m)
{
  struct krus temp;
  for (int i=۰;i<m;i++)
  for (int j=i+1;j<m;j++)
  if (ed[j].weight<ed[i].weight)
  {
  temp=ed[i];
  ed[i]=ed[j];
  ed[j]=temp;
  }
}

• نظریه گراف‌ها و کاربردهای آن، جی.ای. باندی و یو.اس.ار. مورتی. مترجم حمید ضرابی زاده، مؤسسه فرهنگی دیباگران تهران، ۱۳۷۸
• http://en.wikipedia.org/wiki/Kruskal_algorithm