سورس الگوریتم کراسکال در زبان جاوا

سورس الگوریتم کراسکال در زبان جاوا

سلام خدمت شما دوستان 

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

در این پروژه این روند رو پیش بگیرید :

ابتدا یک گراف با تعداد راس مورد نظر ایجاد میکنیم.
با کلیک کردن روی راس ابتدایی و انتهایی و وارد کردن وزن ,یال ها را یکی یکی رسم میکنیم.
می توانیم کراسکال گراف رسم شده را ببینیم.
می توانیم محل راس ها را با نگه داشتن شیفت و کلیک کردن روی یک راس و محل جدید آن تغییردهیم.
با تنظیم کردن زمان می توانیم حالت آهسته ی رسم کراسکال گراف را ببینیم.
می توانیم گراف را در فایل ذخیره و بازیابی کنیم.
ذخیره ی گراف با کلیک رو ی دکمه ی Save و انتخاب فرمت Graph File صورت میگیرد.
بازکرن گراف با کلیک روی فایل گراف یا درگ کردن آن روی برنامه صورت میگیرد.
آخرین گراف رسم شده در هنگام باز شدن نرم افزار به صورت خودکار بازیابی میشود.
میتوانیم گراف را به صورت یه فایل انیمیشن ذخیره کنیم و عملیات رسم کراسکال گراف را ببینیم
این فایل با پسوند .gif ذخیره شده و با مرورگر و … قابل باز شدن است. این انیمیشن برای جنبه های آموزشی نیز کاربرد دارد.

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

در نظریه گراف، الگوریتم کراسکال الگوریتمی برای یافتن یک زیرگراف فراگیر همبند با کمترین وزن در یک گراف وزن‌دار است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شده‌است). همچنین این الگوریتم برای یافتن کوچکترین درخت فراگیر در یک گراف وزن دار استفاده می‌شود.

به عنوان مثال فرض کنید یک شبکه راه آهن که تعدادی شهر را به یکدیگر متصل می‌کند در دست احداث است می‌خواهیم با داشتن هزینه{c_{ij}} مربوط به احداث خط مستقیم بین شهرهای {v_i},{v_j} شبکه را طوری طراحی کنیم که مجموع هزینه‌های ساخت به کمترین مقدار خود برسد. با در نظر گرفتن هر شهر به عنوان یک راس از گراف وزن دار با وزن‌های w({v_i},{v_j})={c_{ij}} مسئله به یافتن یک زیر گراف فراگیر همبند با کمترین وزن در یک گراف منجر می‌شود.

فرض کنید وزن‌ها نامنفی هستند بنابراین می‌توانیم تصور کنیم که زیر گراف فراگیر با کمترین وزن یک درخت فراگیر T از G است حال الگوریتم زیر را برای این کار ارائه می‌دهیم.