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

الگوریتم کروسکال Kruskal’s algorithm یک الگوریتم حریصانه (Heuristic) برای یافتن درخت پوشای کمینه MST است. الگوریتم کروسکال، الگوریتمی در نظریه گراف‌ها است که درخت پوشای مینیمم را برای یک گراف همبند وزن دار ( همبندی یعنی حداقل تعداد رأس‌ها یا یال‌هایی است که با حذفشان، ارتباط رأس‌های باقی‌مانده از بین نرود) پیدا می‌کند. یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه راس ها را شامل شود و دارای حداقل هزینه یال ها باشد.

مقدمه

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

درخت پوشای حداقل

درخت يک گراف متصل بدون حلقه است. يک درخت پوشا (spanning tree) زيرگرافی از گراف G است که شامل کليه رئوس گراف G باشد و يک درخت باشد. بنابراين اگر گراف G دارای n گره باشد درخت پوشای آن دارای n-1 یال است. پیمایش‌های DFS و BFS هر کدام يک درخت پوشا تولید می‌كنند. تعداد درخت‌های پوشای یك گراف كامل با n گره برابر 2n-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 است.

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

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

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

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

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

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

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

مراحل تشکیل الگوریتم کروسکال 1

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

مراحل تشکیل الگوریتم کروسکال 2

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

مراحل تشکیل الگوریتم کروسکال 3

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

مراحل تشکیل الگوریتم کروسکال 4

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

مراحل تشکیل الگوریتم کروسکال 5

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

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

مراحل تشکیل الگوریتم کروسکال 6

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

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

مراحل تشکیل الگوریتم کروسکال 7

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

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

مراحل تشکیل الگوریتم کروسکال 8

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

محصولات مرتبط

مطالب زیر را حتما بخوانید

دیدگاه ها

  1. programstore گفت:

    نطرات و دیدگاه های خود را با ما در میان بگذارید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.