الگوریتم پریم، الگوریتمی در نظریه گرافها است که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا میکند یعنی زیرمجموعهای از یالها را در آن گراف مییابد که درختی را تشکیل میدهند که همه رئوس را شامل میشود در حالیکه مجموع وزن همه آن یالها کمینه شدهاست.
این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد و سپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. از این رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته میشود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.
پاورپوینت الگوریتم موازی prim بیشتر با توضیحات عملی و مثال سعی دارد الگورتیم موازی را شرح دهد.
این الگوریتم مرتبسازی درخت را که از یک یال شروع شدهاست، افزایش میدهد تا جایی که که همه رئوس وارد درخت شوند.
این الگوریتم را بهطور خلاصه میتوان چنین شرح داد:
نکته: الگوریتم پریم را به این صورت نیزمی توان بیان کرد:ابتدا گرهای به دلخواه انتخاب شود و سپس از بین یالهای متصل به آن یالی که با کمترین وزن انتخاب میشود متصل شود به گونهای که حلقه ایجاد نشود. در هر مرحله یالی انتخاب میشود که حتماً یکی از دو سرآن جزو مسیر جواب بوده و وزن حداقل داشته باشد. پس در الگوریتم پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه شکل نگیرد.
از آنجا که در الگوریتم پریم در هر مرحله فاصله هر گره با گرههای قبلی مقایسه میشود پس بدیهی است که از مرتبه (n2)Ѳ میباشد که n تعداد رئوس گراف است.
تعدادی از اسلاید این پاورپوینت را در بخش گالری تصویر برایتان آپلود کردیم که میتوانید قبل از خرید مشاهده کنید.
Original price was: 15,400 تومان.9,900 تومانCurrent price is: 9,900 تومان.
