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

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

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

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

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

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

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

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

۱. تمام یال‌ها را به طور صعودی بر حسب وزن مرتب کنید.
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 نشود. در مثال گراف ورودی را در نظر بگیرید.

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

After sorting:
Weight   Src    Dest
۱         ۷      ۶
۲         ۸      ۲
۲         ۶      ۵
۴         ۰      ۱
۴         ۲      ۵
۶         ۸      ۶
۷         ۲      ۳
۷         ۷      ۸
۸         ۰      ۷
۸         ۱      ۲
۹         ۳      ۴
۱۰        ۵      ۴
۱۱        ۱      ۷
۱۴        ۳      ۵

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

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

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

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

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

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

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

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

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

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

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

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

سخن آخر

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

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

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

کلیک کنید