الگوریتم کروسکال Kruskal’s algorithm

مقدمه پست الگوریتم کروسکال Kruskal’s algorithm

همانطور که گفته شد با توجه به یک گراف متصل و همبند، درخت پوشا از آن گراف یک زیرگراف است که یک درخت است و تمام رأس‌ها را با یکدیگر متصل می‌کند. یک گراف تنها می‌تواند انواع درخت‌های مختلف را پوشش دهد. یک درخت پوشای کمینه (MST) یا درخت پوشای مینیمم درختی برای یک گراف وزن دار، متصل  یک درخت پوشا با وزن کم‌تر یا برابر با وزن هر درخت دیگر است. وزن یک درخت، مجموع وزن‌های داده شده به هر لبه درخت است.

درخت پوشای کمینه Minimum Spanning Tree

درخت يک گراف متصل بدون حلقه است. يک درخت پوشا (Spanning Tree) زيرگرافی از گراف G است که شامل کليه رئوس گراف G باشد و يک درخت باشد. بنابراين اگر گراف G دارای n گره باشد درخت پوشای آن دارای n-1 یال nhvn. پیمایش‌های DFS و BFS هر کدام يک درخت پوشا تولید می‌كنند. تعداد درخت‌های پوشای یك گراف كامل با n گره برابر 2^n-1-1  است.

درخت پوشای حداقل (Minimum Spanning Tree) گراف وزن دار G، درخت پوشائی است که مجموع وزن‌های آن حداقل باشد. برای بدست آوردن درخت پوشای حداقل  الگوريتم کروسکال (Kruskal) و الگوريتم پريم (Prim) و الگوریتم سولین (Sollin) به روش حریصانه شروع به حل مسئله می‌کنند. دو الگوریتم پریم و کروسکال بطور کامل در همین سایت بررسی شده‌اند. در ادامه به بررسی و تشریح الگوريتم کروسکال خواهیم پرداخت.

الگوریتم کروسکال Kruskal’s algorithm

گراف G با n رأس را در نظر بگيريد. الگوريتم کروسکال به صورت زير عمل می‌کند:

1. تمام یال‌ها را به طور صعودی بر حسب وزن مرتب کنید.
2. درخت T را متشکل از گره‌های G بدون یال را ايجاد کنيد.
3. عملیات زیر را n-1 بارتکرار کنید:
4. یک یال با حداقل وزن را به درخت T اضافه کنید به طوری که حلقه ایجاد نشود.

گاهی چند يال دارای يک وزن هستند، در اين حالت ترتيب يال‌هایی که انتخاب می‌شوند مهم نيست. درخت‌های پوشای حداقل مختلفی ممکن است حاصل شود اما مجموع وزن آنها هميشه يکسان و حداقل می‌شود. پيچيدگی زمانی الگوريتم (O(mn می‌شود. که m تعداد يال‌ها و n تعداد رئوس گراف G است.

شبه کد الگوریتم کروسکال

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

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

این الگوریتم یک الگوریتم حریصانه است پس انتخاب حریصانه انتخاب کوچکترین (کم هزینه ترین) وزن  لبه است که باعث ایجاد چرخه ای در MST نشود. در مثال گراف ورودی را در نظر بگیرید.

این گراف شامل 9 رأس و 14 لبه است بنابراین، حداقل درخت پوشا تشکیل شده (9 – 1) = 8 لبه خواهد بود. ابتدا لبه‌ها را به ترتیب کوچکتر به بزرگتر یعنی صعودی مرتب می‌کنیم.

After sorting:
Weight   Src    Dest
1         7      6
2         8      2
2         6      5
4         0      1
4         2      5
6         8      6
7         2      3
7         7      8
8         0      7
8         1      2
9         3      4
10        5      4
11        1      7
14        3      5

حالا همه لبه‌ها را یک به یک از فهرست لبه‌های مرتب شده انتخاب کنید.

1- لبه 6-7 را انتخاب کنید: حلقه‌ای شکل نمی‌گیرد لبه به MST اضافه شود.

2- لبه 2-8 را انتخاب کنید: حلقه‌ای شکل نمی‌شود پس لبه به MST اضافه شود.

3- لبه 6-5 را انتخاب کنید: حلقه‌ای شکل نمی‌شود پس لبه به MST اضافه شود.

4- لبه 0-1 را انتخاب کنید: حلقه‌ای شکل نمی‌شود پس لبه به MST اضافه شود.

6- لبه 8-6 را انتخاب کنید: حلقه شکل می‌شود پس لبه به MST اضافه نمی‌شود.

7- لبه 2-3 را انتخاب کنید: حلقه‌ای شکل نمی‌شود پس لبه به MST اضافه شود.

8- لبه 7-8 را انتخاب کنید: حلقه شکل می‌شود پس لبه به MST اضافه نمی‌شود.

9- لبه 0-7 را انتخاب کنید: حلقه‌ای شکل نمی‌شود پس لبه به MST اضافه شود.

10- لبه 1-2 را انتخاب کنید: حلقه شکل می‌شود پس لبه به MST اضافه نمی‌شود.

11- لبه 3-4 را انتخاب کنید: حلقه‌ای شکل نمی‌شود پس لبه به MST اضافه شود.

از آنجا که تعداد لبه‌ها برابر است 8=(9-1)، الگوریتم در اینجا متوقف می‌شود.

سخن آخر

در پست الگوریتم کروسکال اطلاعاتی درباره این الگوریتم حریصانه که الگوریتمی در نظریه گراف‌ها است و چگونگی استفاده از آن برای یافتن درخت پوشای کمینه MST خدمت شما عزیزان ارائه گردیده است. توضیحات درخت پوشای کمینه،الگوریتم کروسکال و شبه کدهای این الگوریتم به همراه شکل‌ آن‌ها از جمله موارد مهمی است که در این پست شرح داده شده اند.

تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ

تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ

کلیک کنید