الگوریتم Kruskal مولد پیچ و خم

الگوریتم کروسکال یک الگوریتم درخت پوشا حداقل است که می تواند برای تولید پیچ و خم سازگار شود. به ویژه برای ایجاد پیچ و خم های عالی موثر است. جایگزینی برای الگوریتم Kruskal الگوریتم Prim است که همچنین یک الگوریتم درخت پوشا حداقل است، اما از آنجایی که آنها پیچ و خم های یکسانی ایجاد می کنند و Kruskal سریعتر اجرا می شود، من به خود زحمت اجرای Prim را نداده ام.

پیچ و خم کامل، پیچ و خم هایی است که در آن دقیقاً یک مسیر از هر نقطه در پیچ و خم به هر نقطه دیگر وجود دارد. این بدان معناست که شما نمی توانید در نهایت به دور زدن در دایره بپردازید، اما اغلب با بن بست هایی روبرو می شوید که شما را وادار می کند که بچرخید و به عقب برگردید.

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

درباره الگوریتم Kruskal

الگوریتم کروسکال توسط جوزف برنارد کروسکال جونیور، ریاضیدان، آماردان و دانشمند کامپیوتر آمریکایی ایجاد شد. او برای اولین بار این الگوریتم را در سال 1956 در مقاله خود با عنوان "در مورد کوتاه ترین زیر درخت یک نمودار و مسئله فروشنده دوره گرد" توصیف کرد.

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

الگوریتم Kruskal برای تولید پیچ و خم چگونه کار می کند؟

مرحله 1: مقداردهی اولیه

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

مرحله 2: مرتب سازی دیوارها

• دیوارها را به هم بزنید یا به طور تصادفی مرتب کنید. اگر آن را به عنوان یک الگوریتم Kruskal واقعی پیاده سازی می کنید، دیوارها را به ترتیب تصادفی مرتب کنید (زیرا تولید پیچ و خم نیازی به وزن ندارد).

مرحله 3: دیوارهای فرآیند

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

مرحله 4: تا زمان تکمیل ادامه دهید

• این روند را تکرار کنید تا همه سلول ها به هم متصل شوند و یک درخت پوشا تشکیل دهند.
• در پایان، هر سلول بدون حلقه یا بخش های جدا شده به سلول های دیگر متصل می شود.

از آنجایی که الگوریتم Kruskal به ادغام مجموعه ها متکی است، می توان آن را با استفاده از الگوریتم Union-Find بهینه کرد که راهی کارآمد برای ردیابی سلول های متصل در طول تولید پیچ و خم ارائه می دهد. شما می توانید پیاده سازی PHP الگوریتم Union-Find را در اینجا مشاهده کنید: مجموعه مجزا (الگوریتم Union-find) در PHP