الگوريتم درخت پوشای مینیمم ( Minimum Spanning Tree )

http://pnu-club.com/imported/mising.jpg
فرض کنید که یک طراح شهری می خواهد چند شهر را با جاده هایی به هم متصل کند . به طوری که امکان حرکت از هر شهری به شهر دیگر وجود داشته باشد . اگر برای طراحی این جاده ها بودجه محدود پیش بینی شده باشد ، او احتمالا در طراحی خود حداقل طول جاده ها را در نظر می گیرد . هدف مسئله درخت پوشای مینیمم ارائه الگوریتمی برای حل چنین مسائلی می باشد .

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

از میان الگوریتم های مختلفی که برای یافتن درخت پوشای مینیمم وجود دارد در این برنامه از الگوریتم های پریم و دیکسترا استفاده شده است . پس از طراحی گراف مورد نظر می توانید با استفاده از الگوریتم های یاد شده درخت پوشای مینیمم را به دست آورید .

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

ترسیم گراف در صفحه ترسیم
صفحه ترسیم در سمت راست فرم قرار دارد . برای قرار دادن گره ها بر روی این صفحه کافی است بر روی نقطه مورد نظر یک بار کلیک کنید . با یک بار کلیلک کردن بر روی صفحه ترسیم گره ای به صفحه اضافه می شود . برای حذف گره نیز می توانید بر روی گره مورد نظر دابل کلیک کنید . برای انتخاب گره نیز کافی است بر روی گره یک بار کلیک کنید . گره انتخاب شده رنگ متفاوتی نسبت به سایر گره ها خواهد داشت .

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

ترسیم یال از گره 1 به گره 2
ابتدا با کلیک کردن بر روی گره 1 آن گره را انتخاب کنید . سپس کلید Ctrl را فشار داده و و بر روی گره 2 کلیک کنید . در این هنگام یالی بین گره 1 و گره 2 ترسیم می شود . در صورتی که یالی بین گره اول و گره دوم وجود داشته باشد و سعی در ترسیم دوباره یال داشته باشید ، برنامه از ترسیم یال خودداری کرده و سیگنالی را برای آگاهی شما پخش می کند .

می توانید نقشه ترسیم شده را ذخیره کرده و یا نقشه ذخیره شده ای را باز کنید . برای این منظور می توانید از دکمه های قرار گرفته بر روی فرم استفاده کنید . دکمه New یک صفحه ترسیم جدید باز می کند . دکمه Load فایل نقشه را باز می کند و دکمه Save نقشه ترسیم شده را ذخیره می کند .