دانلود کد برنامه نویسی Kruskal Algorithm

موضوع پروژه: سورس کد برنامه پیدا کردن درخت پوشای مینیمم به وسیله الگوریتم کراسکال و زبان برنامه نویسی سی شارپ

 مسیر یابی داخل شهری و بین شهری.

زبان برنامه نویسی: سی شارپ CSharp (C#)

محیط برنامه نویسی: ویژوال استودیو  ( Visual Studio ) ویژال استودیو 2010

توضیحات از ویکی پدیا :

درخت پوشای کمینه یا درخت فراگیر مینیمم در گراف‌های ارزش دار (وزن دار) ساخته می‌شود.

فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل می توان از الگوریتم‌های متفاوتی استفاده نمود.سه الگوریتم معروف پیدا کردن درخت پوشای کمینه عبارتند از : الگوریتم کروسکال، الگوریتم پریم، الگوریتم بروکا(سولین)، الگوریتم حذف معکوس

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

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

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

1. یال پیوندی e 1 {\displaystyle e_{1}} را طوری انتخاب کن که وزن آن کوچکترین مقدار موجود باشد.
2. اگر یال‌های e i + 1 , . . . e 2 , e 1 {\displaystyle {e_{i+1}},{…}{e_{2}},{e_{1}}} انتخاب شده‌اند یال e i + 1 {\displaystyle {e_{i+1}}} را از میان E − e 1 , e 2 , . . . , e i {\displaystyle E-{{e1},{e_{2}},{…},{e_{i}}}} به گونه‌ای انتخاب کن که:
   • زیرگراف با یال‌های e 1 , e 2 , . . . , e i + 1 {\displaystyle {e_{1}},{e_{2}},{…},{e_{i+1}}} بدون دور باشد.
   • از میان یال‌های مشمول شرط (الف) وزن e i + 1 {\displaystyle {e_{i+1}}} دارای کمترین مقدار ممکن باشد.
3. در صورتی که مرحله ۲ دیگر قابل اجرا نیست توقف کن.

نمونه تصاویر خروجی:

ویژگی های این برنامه:

1. رسم گراف به صورت گرافیکی با تعیین وزن یال ها

4. اجرای الگوریتم کراسکال بر روی گراف رسم شده و نمایش هزینه و خروجی گرافیکی با الگوریتم کراسکال

راهنمای اجرا و رسم گراف ها:

پس از اجرای برنامه ابتدا رئوس گراف را با استفاده از کلیک چپ موس بر روی صفحه قرار دهید

سپس کلید Ctrl  را نگاه دارید و دو راسی که میخواهید به هم متصل شوند را کلیک کنید بر رویشان و سپس در پنجره باز شده مقدار وزن یال را قرار دهید

آنچه تحویل داده می شود:

1. کد برنامه قابل اجرا در ویژال استودیو 2010 به بعد – خروجی طبق تصویر نمونه آورده شده (این برنامه درVisual Studio 2010 تست شده و 100 درصد به صورت تضمینی قابل اجرا می باشد)

2. فایل اجرایی برنامه

در صورتی که بخواهید می توانیم با قیمتی مناسب داکیومنت توضیحات این پروژه را تهیه کرده و تقدیم نماییم.

مناسب برای دانشجویان کارشناسی (لیسانس) و کاردانی و کارشناسی ارشد

 می توان به عنوان پروژه دروس کارشناسی یا کاردانی یا کارشناسی ارشد، دروسی مانند هوش مصنوعی، طراحی الگوریتم ها ، ژنتیک ، الگوریتم های پیشرفته ، هوش مصنوعی پیشرفته

توجه توجه توجه: هرگونه کپی برداری و فروش فایل های فروشگاه برکت الکترونیک (به آدرس ebarkat.ir یا codes.sellfile.ir) در فروشگاه های دیگر شرعاً حرام است، تمامی فایل ها و پروژه های موجود در فروشگاه، توسط ما اجرا و پیاده سازی و یا از منابع معتبر زبان اصلی جمع آوری شده اند و دارای حق کپی رایت اسلامی می باشند.

از پایین همین صفحه (بخش پرداخت و دانلود) می توانید این پروژه را خریداری و دانلود نمایید.

کد محصول 30156