الگوریتم پریم Prim’s Algorithm

الگوریتم پریم Prim’s Algorithm

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

مقدمه

این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد و سپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. از این رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته می‌شود که برگرفته از اسامی دایکسترا، جارنیک و پریم است. از این نوع دسته الگوریتم ها می توان به الگوریتم کروسکال و سولین نیز اشاره کرد.

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

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

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

مثال الگوریتم پریم

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

گراف همبند وزدار

مجموعه mstSet در ابتدا خالی است و کلید های اختصاص داده شده به رأس ها عبارتند از {0، INF، INF، INF، INF، INF، INF، INF} که INF نشان دهنده بی نهایت است. ابتدا رأس با حداقل مقدار کلیدی انتخاب می شود. بنابراین {mstSet {0 می شود. پس از وارد شدن به mstSet، مقادیر کلیدی رأس های مجاور را به روز رسانی کنید. رأس های مجاور 0 راس های 1 و 7 هستند. وزن راس های 1 و 7 به ترتیب 4 و 8 به روز می شوند. پس از زیرگراف ردیف ها و مقادیر کلیدی آنها را نشان می دهد، تنها رأس ها با مقادیر کلید محدود نمایش داده می شوند. راس های موجود در MST در رنگ سبز نشان داده شده است.

تشکیل گراف با الگوریتم پریم 1

رأس با حداقل مقدار کلیدی را انتخاب کنید که در MST (نه در mstSET) موجود نیست. رأس 1 برداشته شده و به mstSet اضافه می شود. بنابراین mstSet اکنون {0، 1} می شود. مقدار کلیدی رأس های مجاور 1 را به روز رسانی کنید. مقدار کلیدی رأس 2 به 8 می رسد.

تشکیل گراف با الگوریتم پریم 2

دوباره رأس با حداقل مقدار کلیدی را انتخاب کنید که در MST (نه در mstSET) موجود نیست. ما می توانیم راس 7 یا راس 2 را انتخاب کنیم، راس 7 را انتخاب کنیم. بنابراین mstSet اکنون {0، 1، 7} می شود. ارزش کلیدی رأس های مجاور 7 را به روز رسانی کنید. مقدار کلیدی رأس 6 و 8 به ترتیب محدود می شود (1 و 7 به ترتیب).

تشکیل گراف با الگوریتم پریم 3

باز رأس با حداقل مقدار کلیدی را انتخاب کنید که در MST موجود نیست. راس 6 برداشته می شود. بنابراین mstSet اکنون {0، 1، 7، 6} می شود. ارزش کلیدی رأس های مجاور 6 را به روز کنید. ارزش کلیدی رأس 5 و 8 به روز می شود.

تشکیل گراف با الگوریتم پریم 4

گام های فوق را تکرار کنید تا mstSet شامل تمام رأس های گراف داده شده باشد. در نهایت، ما نمودار زیر را بدست می آوریم.

تشکیل گراف با الگوریتم پریم 4

 

محصولات مرتبط

مطالب زیر را حتما بخوانید

دیدگاه ها

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.