برنامه نویسی 340 بازدید

در این مقاله ابتدا با مفهوم درخت‌های پوشای کمینه آشنا می‌شویم. سپس از الگوریتم پریم در جاوا برای یافتن چنین درختی استفاده می‌کنیم.

درخت پوشای کمینه

منظور از «درخت پوشای کمینه» (minimum spanning tree) یا به اختصار MST یک گراف وزن‌دار، غیر جهت‌دار و همبند است که وزن کلی یال‌های آن با حذف یال‌های سنگین‌تر به کمترین مقدار ممکن رسیده باشد. به بیان دیگر ما همه رئوس گراف را دست‌نخورده حفظ می‌کنیم، اما ممکن است برخی یال‌ها را حذف کنیم به طوری که مجموعه وزن همه یال‌ها به کمینه مقدار برسد.

کار خود را با یک گراف وزن‌دار آغاز می‌کنیم، زیرا کمینه‌سازی وزن کلی یال در صورتی که این یال‌ها کلاً وزنی نداشته باشند، معنی نخواهد داشت. در تصویر زیر مثالی از این نوع گراف می‌بینید:

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

گراف فوق وزن‌دار، غیر جهت‌دار و همبند است. MST این گراف به صورت زیر است:

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

توجه کنید که درخت پوشای کمینه گراف، یکتا نیست. از این رو اگر گراف بیش از یک MST داشته باشد، هر MST وزن یال مجموع یکسانی خواهد داشت.

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

الگوریتم پریم (Prim) یک گراف وزن‌دار، غیر جهت‌دار و همبند به عنوان ورودی می‌گیرد و یک MST از گراف به عنوان خروجی بازگشت می‌دهد. این الگوریتم به روش حریصانه کار می‌کند. در گام نخست یک رأس دلخواه انتخاب می‌شود، سپس در هر گام جدید نزدیک‌ترین رأس به درختی که تا اینجا ساخته شده اضافه می‌شود تا این که هیچ رأس غیر همبندی نماند. در ادامه الگوریتم پریم را روی گراف مثال فوق به صورت گام به گام اجرا می‌کنیم:

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

با فرض رأس دلخواه شروع روی رأس B، گزینه‌های A ،C و E را در اختیار داریم. وزن‌های متناظر این یال‌ها به ترتیب برابر با 0، 0 و 5 است. از این رو کمینه آن یعنی 2 را انتخاب می‌کنیم. از آنجا که در این مثال دو یال را وزن 2 داریم، می‌توانیم هر کدام از آن‌ها را انتخاب کنیم. فعلاً این که کدام را انتخاب می‌کنیم اهمیتی ندارد. برای مثال فرض کنید رأس A را انتخاب می‌کنیم:

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

اکنون درختی با دو رأس A و B داریم می‌توانیم هر کدام از یال‌های A یا B را که هنوز اضافه نشده به یک رأس اضافه نشده انتخاب کنیم. بنابراین می‌توانیم AC ،BC یا BE را انتخاب کنیم. الگوریتم پریم مقدار مینیمم را انتخاب می‌کند که برابر با 2 یا BC است.

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

اکنون درختی با سه رأس و سه یال ممکن برای حرکت به جلو به صورت CD ،CE یا BE داریم. AC در این لیست نیست، زیرا رأس جدیدی به درخت اضافه نمی‌کند. کمینه وزن در میان این سه یال برابر با 1 است. با این حال دو یال وجود دارند که هر دو وزن 1 دارند. در نتیجه الگوریتم پریم یکی از آن‌ها را انتخاب می‌کند. این بار نیز مهم نیست کدام را انتخاب می‌کنیم:

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

اینک تنها یک رأس باقیمانده است، بنابراین می‌توانیم از CE و BE انتخاب کنیم. کمینه وزن که درخت ما را وصل کند برابر با 1 است و آن را انتخاب می‌کنیم.

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

از آنجا که همه رئوس گراف ورودی هم اینک در درخت خروجی حاضر هستند، الگوریتم پریم پایان می‌یابد. بدین ترتیب این درخت یک MST از گراف ورودی است.

پیاده‌سازی

رأس‌ها و یال‌ها گراف را می‌سازند، از این رو باید ساحتمان داده‌ای برای ذخیره‌سازی این عناصر داشته باشیم. ابتدا یک کلاس Edge می‌سازیم:

هر Edge باید یک Weight داشته باشد، زیرا الگوریتم پریم روی گراف‌های وزن‌دار کار می‌کند. isIncluded نشان می‌دهد که آیا یال مورد نظر در درخت کمینه‌ی پوشا حضور دارد یا نه. اینک کلاس Vertex را اضافه می‌کنیم:

هر Vertex می‌تواند یک Label داشته باشد، ما از یک map به نام edges برای ذخیره اتصال‌ها میان رئوس استفاده می‌کنیم. در نهایت isVisited نشان می‌دهد که آیا رأس مورد نظر تاکنون از سوی الگوریتم پریم بازدید شده است یا نه. کلاس Prim ما جایی است که منطق را پیاده‌سازی می‌کنیم:

لیستی از رئوس برای ذخیره‌سازی کل گراف کافی است، زیرا درون هر Vertex یک Map<Vertex, Edge>‎ داریم که همه اتصال‌ها را شناسایی می‌کند. درون Prim متد ()run را ایجاد می‌کنیم:

کار خود را با تعیین عنصر نخست گراف List<Vertex>‎ به صورت بازدید شده آغاز می‌کنیم. عنصر اول بسته به ترتیبی که به لیست اضافه شده است، می‌تواند هر یک از رئوس باشد. ()isDisconnected در صورتی مقدار true بازگشت می‌دهد که vertex تاکنون بازدید نشده باشد:

با این که درخت پوشای کمینه به صورت ()isDisconnected است، روی رئوس قبلاً بازدید شده حلقه‌ای تعریف می‌کنیم و آن Edge را که دارای کمترین وزن است به عنوان رأس بعدی برای nextVertex انتخاب می‌کنیم:

بدین ترتیب کمینه همه رئوس بالقوه را در حلقه اصلی می‌یابیم و در nextVertex ذخیره می‌کنیم. سپس nextVertex را به صورت بازدید شده علامت‌گذاری می‌کنیم. این حلقه تا زمانی که همه رئوس بازدید شوند ادامه می‌یابد و در نهایت هر یال با مقدار isIncluded به صورت true در MST حضور دارد.

توجه کنید که چون ()nextMinimum روی یال‌ها می‌چرخد، پیچیدگی زمانی این پیاده‌سازی برابر با O(v^2) است. اگر یال‌ها را در یک صف اولویت (که بر مبنای وزن مرتب‌سازی شده) ذخیره کنیم، این الگوریتم در زمان O(E log V) اجرا می‌شود.

تست کردن

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

سازنده کلاس Prim آن را می‌گیرد و درون کلاس ذخیره می‌کند. می‌توانیم گراف را با متد ()originalGraphToString ذخیره کنیم:

اکنون مثال ما یک خروجی به صورت زیر دارد:

اکنون می‌توانیم الگوریتم پریم را اجرا کرده و نتیجه MST را با متد ()minimumSpanningTreeToString چاپ کنیم:

در نهایت MST را چاپ می‌کنیم:

سخن پایانی

در این مقاله با طرز کار الگوریتم پریم و تشکیل یک درخت پوشای کمینه از یک گراف آشنا شدیم. همه کدهای مطرح شده در این مقاله را می‌توانید در این رپیوی گیت‌هاب (+) ملاحظه کنید.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

میثم لطفی (+)

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

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

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