(186 امتیاز از 51 رای)
Loading...
سورس الگوریتم پریم با فایل به زبان ++C
در این پست از سایت نوآوران گرمی برای شما کاربران عزیز، سورس الگوریتم پریم با فایل به زبان ++C را آماده کرده ایم که امیدواریم مورد استفاده قرار گیرد.
این برنامه سورس کد برنامه جستجوی زیردرخت پوشای کمینه برای یک گراف همبند با استفاده از الگوریتم پریم می باشد. تعداد رئوس گراف و ماتریس وزن ها را چنانکه در تصویر مشاهده می کنید از فایلی به نام “dist.txt” که باید در مسیر فایل اجرایی برنامه باشد، خوانده و یال های درخت پوشای کمینه و مجموع وزن آن ها را به نمایش درمی آورد. در زمان وارد نمودن اطلاعات گراف در فایل، وزن یال رئوسی که با هم ارتباط ندارند را صفر وارد نمایید.
توضیح الگوریتم پریم:
الگوریتم پریم ، الگوریتمی در نظریه گراف‌ها می باشد که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار می یابد یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف پیدا می کند که درختی را تشکیل می‌دهند که همه رئوس را شامل می‌شود در حالیکه مجموع وزن همه آن یال‌ها کمینه شده است.
الگوریتم پریم را به این صورت می توان بیان کرد: ابتدا گره ای به دلخواه انتخاب شود و سپس از بین یال های متصل به آن یالی با کمترین وزن انتخاب می شود به گونه ای که حلقه ایجاد نشود. در هر مرحله یالی انتخاب می شود که باید یکی از دو سرآن جزو مسیر جواب بوده و وزن حداقل داشته باشد. پس درالگوریتم پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه پدید نیاید.
هیچ نظری ثبت نشده است