الگوریتم پریم چگونه کار می کند ؟

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

قبل از بیان الگوریتم پریم یکی از راه های بدست آوردن درخت پوشا کمینه از یک گراف این است که تمام درخت های پوشای گراف را بدست آوریم و بعد آن هایی که کمترین هزینه را دارند را انتخاب کنیم که بسیار هزینه بر است .(تعداد درخت پوشا در یک گراف کامل 2n-1-1 است . )

اما مثال : با الگوریتم پریم می خواهیم درخت پوشای کمینه کراف زیر را بدست آوریم .

در قدم اول یک گره را به طور اختیاری انتخاب می کنیم . ما در این مثال گره صفر را انتخاب می کنیم.

در قدم دوم باید گره هایی که به طور مستقیم به گره صفر وصل شده اند را بررسی کنیم و گره ای که کمترین هزینه را دارد را انتخاب کنیم . همان طور که در شکل زیر مشاهده می شود ، گره صفر به گره 1 با هزینه 4 و به گره 7 با هزینه 8 متصل است .

پریم از آن جایی که الگوریتمی حریصانه است کمترین هزینه را انتخاب می کند . پس گره 1 با هزینه 4 انتخاب می شود .
حال دوباره باید نزدیک ترین گره هایی که به طور مستقیم به گره های انتخاب شده متصل هستند را بررسی کنیم. همانطور که در شکل زیر مشاهده می کنید گره 2 با هزینه 8 به گره 1 متصل است و گره 7 با هزینه 8 به گره صفر متصل است . حال کدام یک انتخاب می شود ؟ وقتی هر دو یک هزینه دارند ! مهم نیست یک گره را به دلخواه انتخاب کنید . ( علت دلخواهی بودن چیست ؟ علت این است که برای یک گراف درخت پوشای کمینه زیادی وجود دارد . یک گراف فقط یک درخت پوشای کمینه ندارد )

نکته : از گره 1 به گره 7 هم یک مسیر وجود دارد و علت این که بررسی نمی شود این است که ایجاد حلقه می کند . پس در تصاویر ما یال هایی که ایجاد حلقه می کنند را ذکر نکردیم .

ما گره هفت را انتخاب کردیم . پس گره هایی که تاکنون حل شده اند : {0,1,7 } . حال دوباره باید گره هایی که به طور مستقیم به گره های حل شده وصل هستند را بررسی کنیم . همان طور که ملاحظه می شود :

گره 2 با هزینه 8 به گره 1

گره 6 با هزینه 1 به گره 7

گره 8 با هزینه 7 به گره 7

گره 6 با هزینه یک انتخاب می شود . پس گره های حل شده عبارتند از : {0,1,7,6} . حال دوباره باید گره هایی که به طور مستقیم به گره های حل شده وصل هستند را بررسی کنیم .

به گره 1 : گره 2 با هزینه 8 وصل است.

یادآوری نکته بالا : گره های وصل شده به هفت را بررسی نمی کنیم چون ایجا حلقه می کنند .

به گره 6 : گره 8 با هزینه 6 و گره 5 با هزینه 2 وصل است .

گره 5 با هزینه 2 انتخاب می شود .

در آخر درخت پوشای کمینه به صورت زیر خواهد بود .

اما مراحلی که ذکر نشد :

به گره 1 : گره 2 با هزینه 8

به گره 6 : گره 8 با هزینه 6

به گره 5 : گره های 2 و 3 و 4 وصل هستند که هزینه هایشان به ترتیب عبارت است از : 4 و 14 و 10 که طبق پریم گره 2 انتخاب می شود .

پس گره های حل شده تا این مرحله {0,1,7,6,5,2 } . حال دوباره نسبت به گره های حل شده دوباره گره های متصل بررسی می شود :

به گره 6 : گره 8 با هزینه 6 وصل است.

به گره 2 : گره 8 با هزینه 2 و گره 3 با هزینه 7 وصل است .

به گره 5 : گره 3 و 4 با هزینه های 14 و 10 وصل است . پس گره با هزینه 2 که به گره 2 وصل است انتخاب می شود .

گره های حل شده {0,1,7,6,5,2,8} . حال دوباره اگر گره های باقی مانده را نسبت به گره های حل شده بررسی کنیم : گره 3 با هزینه 7 به گره دو وصل است . پس گره های حل شده : {0,1,7,6,5,2,8,3}

و در آخر هم گره 4 به گره 3 و گره 5 وصل است که گره 4 را با هزینه 9 به گره 3وصل می کنیم .

منبع

برای درک بهتر الگوریتم پریم می توانید به این صفحه بروید تا مراحل کار یک گراف دیگر را مرحله به مرحله مشاهده کنید .

الگوریتم پریم چگونه کار می کند ؟

مطالب مشابه :

الگوریتم دایجسترا

دانلود پروژه رایگان الگوریتم دایجسترا با نرم افزار MATLAB

مسیریابی شبکه های کامپیوتری

الگوريتم دايكسترا (Dijkstra's algorithm) چيست؟

دانلود رایگان سورس الگوریتم دیکسترا به زبان ++C

الگوریتم‌های مسیریابی

انواع الگوریتم مسیریابی

انواع الگوریتم search

الگوریتم پریم چگونه کار می کند ؟