الگوریتم Sollin سولین تشریح همراه با مثال

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

الگوریتم Boruvka یک الگوریتم حریصانه است و مشابه الگوریتم Kruskal و الگوریتم Prim است. الگوریتم مذکور، اولین الگوریتمی بود که در سال ۱۹۲۶ برای پیدا کردن درخت پوشای کمینه MSTs طراحی شد.

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

الگوریتم Boruvka راهی برای پیدا کردن درخت پوشای کمینه است. یک درخت پوشای مینیمم درختی است که در آن مجموع وزن لبه به حداقل برسد. این اولین الگوریتمی بود که در سال ۱۹۲۶ برای پیدا کردن درخت پوشای کمینه MSTs طراحی شد. آقای Otakar Boruvka از آن برای یافتن مسیریابی کارآمدترین شبکه برق استفاده کرده است. الگوریتم‌ها و روش‌های زیادی برای پیدا کردن درخت پوشای حداقل وجود دارد.

الگوریتم Boruvka یک الگوریتم حریصانه است و مشابه الگوریتم Kruskal و الگوریتم Prim است. این روش اساساً حد وسط بین دو الگوریتم کروسکال و پریم است. این الگوریتم اغلب با نام الگوریتم Sollin نیز شناخته می‌شود. در کتاب‌های ساختمان داده اغلب از این روش با نام الگوریتم سولین یاد می‌شود.

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

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

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

۱) Input is a connected, weighted and directed graph.
۲) Initialize all vertices as individual components (or sets).
۳) Initialize MST as empty.
۴) While there are more than one components, do following
   for each component.
      a)  Find the closest weight edge that connects this 
          component to any other component.
      b)  Add this closest edge to MST if not already added.  
۵) Return MST.

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

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

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

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

Component                Cheapest Edge that connects 
                         it to some other component
  {۰}                           ۰-۱
  {۱}                           ۰-۱
  {۲}                           ۲-۸
  {۳}                           ۲-۳
  {۴}                           ۳-۴
  {۵}                           ۵-۶
  {۶}                           ۶-۷
  {۷}                           ۶-۷
  {۸}                           ۲-۸

ارزان ترین لبه با رنگ سبز مشخص شده است. اکنون MST 0-1، ۲-۸، ۲-۳، ۳-۴، ۵-۶، ۶-۷ می‌شود.

بعد از مرحله بالا اجزاء یا همان زیر دختان {{۰،۱}، {۲،۳،۴،۸}، {۵،۶،۷}} می‌باشد. اجزاء با رنگ آبی محاصره می‌شوند.

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

Component                Cheapest Edge that connects 
                         it to some other component
  {۰,۱}                        ۱-۲ (or 0-7)
  {۲,۳,۴,۸}                    ۲-۵
  {۵,۶,۷}                      ۲-۵

در مرحله آخر تنها یک جزء {۰، ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸} وجود دارد که همه لبه‌ها دارد. از آنجا که تنها یک جزء وجود دارد، الگوریتم متوقف می‌شود و درخت ایجاد می‌شود. در نهایت درخت پوشا بصورت زیر خواهد بود و هزینه آن نیز برابر ۳۷ خواهد بود.

سخن آخر

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

ارائه درباره الگوریتم دایجسترا

ارائه درباره الگوریتم دایجسترا

کلیک کنید