الگوریتم سولین Sollin

الگوریتم Boruvka (الگوریتم Sollin)

الگوریتم Sollin یا همان الگوریتم Boruvka عنوان موضوعی است که در این پست به آن پرداخته می شود. ابتدا الگوریتم سولین تشریح می شود سپس مثال عملی از این الگوریتم زده می شود. برای اطلاهات بیشتر روی مفاهیم موجود در این پست به لینک هایی که گذاشته شده حتماً مراجعه کنید.

الگوریتم بروکا Boruvka چیست؟

الگوریتم Boruvka راهی برای پیدا کردن درخت پوشای کمینه است. یک درخت پوشای مینیمم درختی است که در آن مجموع وزن لبه به حداقل برسد. این اولین الگوریتمی بود که در سال 1926 برای پیدا کردن درخت پوشای کمینه MSTs طراحی شد.  آقای Otakar Boruvka از آن برای یافتن مسیریابی کارآمدترین شبکه برق استفاده کرده است. الگوریتم ها و روش های زیادی برای پیدا کردن درخت پوشای حداقل وجود دارد. الگوریتم Boruvka یک الگوریتم حریصانه است و مشابه الگوریتم Kruskal و الگوریتم Prim است. این روش اساساً حد وسط بین دو الگوریتم کروسکال و پریم است. این الگوریتم اغلب با نام الگوریتم Sollin نیز شناخته می شود. در کتاب های ساختمان داده اغلب از این روش با نام الگوریتم سولین یاد می شود.

تشریح الگوریتم Sollin

بر خلاف الگوریتم های پریم و راشال – کروسکال که در هر مرحله فقط یک یال به درخت اضافه می کردند در الگوریتم سولین چندین لبه را برای درخت اضافه می کند. در ابتدا یک مرحله لبه های انتخاب شده، همراه با تمام n راس گراف، تشکیل یک درخت پوشا را می دهند. در خلال یک مرحله یک لبه برای هر درخت انتخاب می شود که دارای حداقل هزینه بوده یعنی اینکه دقیقاً دارای یک راس در درخت می باشد. از آنجا که دو درخت در جنگل می توانند یک لبه یکسان انتخاب کنند، لذا می توان کپی تکراری لبه ها را حذف کرد. در ابتدای مرحله اول مجموعه لبه های انتخاب شده خالی است. این الگوریتم هنگامی پایان می یابد که فقط یک درخت در انتهای یک مرحله باقی و یا هیچ لبه ای برای انتخاب باقی نمانده باشد. شبه کد الگوریتم Boruvka  به صورت زیر است:

مثال الگوریتم سولین (Sollin)

برای مثال گراف شکل زیر را همراه با هزینه هر لبه در نظر می گیریم.

 

گراف الگوریتم سولین 1

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

گراف الگوریتم سولین 2

برای هر جزء، ارزان ترین لبه را پیدا کنید که آن را به یک جزء دیگر متصل می کند.

ارزان ترین لبه با رنگ سبز مشخص شده است. اکنون MST 0-1، 2-8، 2-3، 3-4، 5-6، 6-7 می شود.

گراف الگوریتم سولین 3

بعد از مرحله بالا اجزاء یا همان زیر دختان {{0،1}، {2،3،4،8}، {5،6،7}} می باشد. اجزاء با رنگ آبی محاصره می شوند.

گراف الگوریتم سولین 4

در مرحله بعد دوباره گام قبلی را برای مشخص کردن ارزان ترین لبه تکرار می کنیم، به عنوان مثال، برای هر جزء، ارزان ترین لبه را پیدا می کنیم که آن را به برخی اجزای دیگر متصل می کند ( یعنی به درختان دیگر متصل کند نه اعضای جزء خودش)

گراف الگوریتم سولین 5

در مرحله آخر تنها یک جزء {0، 1، 2، 3، 4، 5، 6، 7، 8} وجود دارد که همه لبه ها دارد. از آنجا که تنها یک جزء وجود دارد، الگوریتم متوقف می شود و درخت ایجاد می شود. در نهایت درخت پوشا بصورت زیر خواهد بود و هزینه آن نیز برابر 37 خواهد بود.

گراف الگوریتم سولین 6

 

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

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

دیدگاه ها

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

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

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