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

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 {e_{1}},{e_{2}},{...},{e_{v-1}}}$ که با الگوریتم کراسکال ساخته شود یک درخت بهینه‌است.

از طریق تناقض: به ازای هر درخت فراگیر ${\displaystyle T}$ از ${\displaystyle G}$ به غیر از ${\displaystyle U}$ کوچکترین مقدار ${\displaystyle i}$ را به طوری که ${\displaystyle {e_{i}}}$ در ${\displaystyle T}$ نباشد با${\displaystyle f(t)}$ نمایش می‌دهیم. اکنون فرض کنید که ${\displaystyle U}$ یک درخت بهینه نباشد و ${\displaystyle T}$ را به عنوان درخت بهینه در نظر بگیرید که در آن${\displaystyle f(t)}$ دارای بزرگترین مقدار ممکن باشد. فرض کنید ${\displaystyle f(t)=k}$ این بدان معنی است که ${\displaystyle {e_{k-1}},{...},{e_{2}},{e_{1}}}$ هم در ${\displaystyle T}$ و هم در ${\displaystyle U}$ هستند؛ ولی ${\displaystyle {e_{k}}}$ در ${\displaystyle T}$ نیست پس شامل یک دور یکتای ${\displaystyle C}$ می‌باشد. فرض کنید ${\displaystyle {{e^{'}}_{k}}}$ یالی از ${\displaystyle C}$ باشد که در ${\displaystyle T}$ هست ولی در ${\displaystyle U}$ نیست. پس ${\displaystyle {{e^{'}}_{k}}}$یال برشی ازT+${\displaystyle {e_{k}}}$ نیست؛ بنابراین ${\displaystyle {T^{'}}=(T+{e_{k}}-{{e^{'}}_{k}})}$ یک گراف همبند با ${\displaystyle v-1}$ یال بوده در نتیجه درخت فراگیر دیگری برای ${\displaystyle G}$ خواهد بود. روشن است که:

${\displaystyle w({T^{'}})=w(T)+w({e_{k}})-w({{e^{'}}_{k}})}$

ولی در الگوریتم کراسکال ${\displaystyle {e_{k}}}$ به عنوان یالی با کمترین وزن طوری انتخاب شده‌است که زیرگراف ${\displaystyle G}$ با یال‌های ${\displaystyle {e_{k}},{...},{e_{2}},{e_{1}}}$ بدون دور باشد. چون زیرگراف ${\displaystyle G}$ با یال‌های ${\displaystyle {{e^{'}}_{k}},{...},{e_{2}},{e_{1}}}$ زیر گرافی از ${\displaystyle T}$ است. بنابرین ان هم بدون دور است و نتیجه می‌گیریم که:

${\displaystyle w({{e^{'}}_{k}})}$ ≥ ${\displaystyle w({{e}_{k}}),}$

پس

${\displaystyle w({T^{'}})}$ ≤ ${\displaystyle w({T}),}$

پس ${\displaystyle {T^{'}}}$ هم یک درخت بهینه خواهد بود در صورتی که داریم:

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

که این با ${\displaystyle T}$ انتخاب در تناقض است. بنابرین ${\displaystyle T=U}$ و در نتیجه${\displaystyle U}$ یک درخت بهینه‌است.

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

ورودی:عدد صحیح 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