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

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

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

مقدمه

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

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

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

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

۱) Create a set mstSet that keeps track of vertices already included in MST.
۲) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
۳) While mstSet doesn’t include all vertices
….a) Pick a vertex u which is not there in mstSet and has minimum key value.
….b) Include u to mstSet.
….c) Update key value of all adjacent vertices o

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

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

مجموعه mstSet در ابتدا خالی است و کلیدهای اختصاص داده شده به رأس‌ها عبارتند از {۰، INF، INF، INF، INF، INF، INF، INF} که INF نشان دهنده بی نهایت است. ابتدا رأس با حداقل مقدار کلیدی انتخاب می‌شود. بنابراین {mstSet {0 می‌شود. پس از وارد شدن به mstSet، مقادیر کلیدی رأس‌های مجاور را به روز رسانی کنید. رأس‌های مجاور ۰ راس های ۱ و ۷ هستند. وزن راس‌های ۱ و ۷ به ترتیب ۴ و ۸ به روز می‌شوند. پس از زیرگراف ردیف‌ها و مقادیر کلیدی آنها را نشان می‌دهد، تنها رأس‌ها با مقادیر کلید محدود نمایش داده می‌شوند. راس‌های موجود در MST در رنگ سبز نشان داده شده است.

رأس با حداقل مقدار کلیدی را انتخاب کنید که در MST (نه در mstSET) موجود نیست. رأس ۱ برداشته شده و به mstSet اضافه می‌شود. بنابراین mstSet اکنون {۰، ۱} می‌شود. مقدار کلیدی رأس‌های مجاور ۱ را به روز رسانی کنید. مقدار کلیدی رأس ۲ به ۸ می‌رسد.

دوباره رأس با حداقل مقدار کلیدی را انتخاب کنید که در MST (نه در mstSET) موجود نیست. ما می‌توانیم راس ۷ یا راس ۲ را انتخاب کنیم، راس ۷ را انتخاب کنیم. بنابراین mstSet اکنون {۰، ۱، ۷} می‌شود. ارزش کلیدی رأس‌های مجاور ۷ را به روز رسانی کنید. مقدار کلیدی رأس ۶ و ۸ به ترتیب محدود می‌شود (۱ و ۷ به ترتیب).

باز رأس با حداقل مقدار کلیدی را انتخاب کنید که در MST موجود نیست. راس ۶ برداشته می‌شود. بنابراین mstSet اکنون {۰، ۱، ۷، ۶} می شود. ارزش کلیدی رأس‌های مجاور ۶ را به روز کنید. ارزش کلیدی رأس ۵ و ۸ به روز می‌شود.

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

پاورپوینت آماده در مورد الگوریتم پریم

پاورپوینت آماده در مورد الگوریتم پریم

کلیک کنید