کامپیوتر 195 بازدید

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

به طور رسمی گراف جفتی از مجموعه (V, E) است که در آن V مجموعه از رئوس و E مجموعه‌ای از یال‌ها است که رئوس را به هم متصل می‌سازند. نگاهی به گراف زیر بیندازید:

در گراف فوق:

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

گراف‌های ریاضی را می‌توان به وسیله ساختارهای داده بازنمایی کرد. ما می‌توانیم گراف را با استفاده از آرایه‌ای از رئوس و یک آرایه دو بعدی از یال‌ها نشان دهیم. پیش از آن که به ادامه مطلب بپردازیم، ابتدا با برخی اصطلاح‌های مهم این حوزه آشنا می‌شویم:

  • رأس – هر گره در گراف به شکل یک رأس نمایش می‌یابد. در شکل زیر دایره‌هایی که نوشته دارند رئوس هستند بدین ترتیب نقاطی که با حروف A تا G مشخص شده‌اند، رأس‌های گراف محسوب می‌شوند. آن‌ها را می‌توانیم با استفاده از یک آرایه که در تصویر زیر نمایش یافته است نشان دهیم. در این آرایه A در اندیس 0 قرار دارد، B در اندیس 1 است و همین طور تا آخر.
  • یال – به مسیر بین دو رأس یا خطی که بین رئوس برقرار می‌شود، یال می‌گوییم. در مثال زیر، خط از A تا B، از B تا C و همین طور تا آخر یال‌های گراف محسوب می‌شوند. می‌توان از آرایه‌ای دو بعدی مانند آنچه در تصویر زیر قرار دارد، برای نمایش یال‌های گراف استفاده کرد. در این آرایه AB به معنی یال بین رأس‌های A و B است که در ردیف 0، ستون 1 قرار دارد، یال BC در ردیف 1، ستون 2 و همین طور تا آخر همه یال‌ها مشخص شده‌اند. ترکیب‌هایی که یالی ندارند مقدار صفر دارند.
  • مجاورت – دو گره یا رأس در صورتی مجاور خوانده می‌شوند که از طریق یالی به هم وصل شده باشند. در مثال زیر رأس B با رئوس A و رأس C با B مجاور است.
  • مسیر – به یک توالی از یال‌ها بین دو رأس، مسیر گفته می‌شود. در مثال زیر ABCD نشان دهنده وجود مسیری از رأس A تا D است.

عملیات‌های پایه

در ادامه برخی از عملیات‌های مقدماتی گراف شرح داده شده‌اند:

  • افزودن رأس (Add Vertex): این عملیات یک رأس به گراف اضافه می‌کند.
  • افزودن یال (Add Edge): این عملیات بین دو رأس موجود در گراف یالی برقرار می‌سازد.
  • نمایش رأس (Display Vertex): یک رأس را در گراف نمایش می‌دهد.

پیمایش گراف

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

پیمایش عمق-اول (Depth First)

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

الگوریتم پیمایش عمق-اول همان طور که در شکل فوق مشخص است، ابتدا از S به A به D به G به E به B می‌رود، سپس به F و در نهایت به C می‌رود. قواعد این پیمایش چنین است:

  • قاعده 1: به رأس بازدید نشده مجاور برو. آن را به صورت بازدید شده علامت‌گذاری کن. آن را وارد پشته بکن.
  • قاعده 2: اگر رأس مجاوری نمانده باشد، یک رأس را از پشته pop کنید. (همه رئوسی که رأس‌های مجاور ندارند، از پشته pop می‌شوند).
  • قاعده 3: قاعده 1 و قاعده 2 را تا زمانی که پشته خالی شود، ادامه بده.
گام پیمایش توضیح
1 Depth First Search Step One مقدار دهی اولیه پشته.
2 Depth First Search Step Two رأس S به عنوان رأس بازدید شده نشانه‌گذاری می‌شود و در پشته قرار می‌گیرد. هر گونه گره‌های بازدید نشده مجاور گره S بررسی می‌شوند. سه گره داریم که می‌توانیم هر یک از آن‌ها را انتخاب کنیم. در این مثال، این گره را با ترتیب الفبایی انتخاب می‌کنیم.
3 Depth First Search Step Three رأس A را به عنوان بازدید شده نشانه‌گذاری می‌کنیم و آن را در پشته قرار می‌دهیم. همه گره‌های مجاور بازدید نشده را بررسی می‌کنیم. هر دو گره S و D مجاور A هستند؛ اما ما تنها به دنبال گره‌های بازدید نشده هستیم.
4 Depth First Search Step Four رأس D را به عنوان بازدید شده نشانه‌گذاری می‌کنیم و آن را درون پشته قرار می‌دهیم. در این جا رأس B و C را داریم که مجاور D هستند و هر دو بازدید نشده هستند. با این حال باز هم می‌توانیم با ترتیب الفبایی انتخاب کنیم.
5 Depth First Search Step Five رأس B را انتخاب می‌کنیم و آن را به عنوان بازدید شده نشانه‌گذاری کرده و در پشته قرار می‌دهیم. در این مرحله B هیچ رأس مجاوری ندارد. بنابراین رأس B را از پشته بر می‌داریم (pop).
6 Depth First Search Step Six آیتم top پشته را برای یافتن گره قبلی بررسی می‌کنیم و تست می‌کنیم که آیا گره‌های بازدید نشده دارد یا نه. در این مرحله، D را در بخش top پشته می‌یابیم.
7 Depth First Search Step Seven تنها گره مجاور بازدید نشده رأس‌های D و C هستند. بنابراین از رأس C بازدید می‌کنیم و آن را به عنوان بازدید شده در پشته قرار می‌دهیم.

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

پیاده‌سازی الگوریتم جستجوی عمق-اول در زبان C

مثالی که در بخش فوق را بررسی کردیم را در زبان C مدل‌سازی کرده‌ایم.

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

خروجی

Depth First Search: S A D B C

پیمایش سطح-اول

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

در مثال فوق الگوریتم سطح-اول ابتدا از رأس A به B به E و به F می‌رود و. سپس به C و در نهایت از G به D می‌رود. قواعد این پیمایش چنین هستند:

  • قاعده اول: از رأس بازدید نشده مجاور بازدید کن. آن را به صورت بازدید شده نشانه‌گذاری کن، آن را نمایش بده و در صف درج کن.
  • قاعده 2: اگر هیچ رأس مجاوری وجود ندارد، نخستین رأس را از صف خارج کن.
  • قاعده 3: قواعد 1 و 2 را تا زمانی که صف خالی شود ادامه بده.
گام پیمایش توضیح
1 Breadth First Search Step One مقداردهی اولیه صف
2 Breadth First Search Step Two کار خود را از رأس S (گره آغازین) شروع می‌کنیم و آن را بازدید شده نشانه‌گذاری می‌کنیم.
3 Breadth First Search Step Three سپس می‌بینیم که در S یک گره مجاور بازدید نشده وجود دارد. در این مثال، سه گره داریم؛ اما به صورت الفبایی رأس A را انتخاب می‌کنیم، آن را به صورت بازدید شده نشانه‌گذاری کرده وارد صف می‌کنیم.
4 Breadth First Search Step Four سپس می‌بینیم که گره مجاور بازدید نشده از S، گره B است. آن را به عنوان بازدید شده نشانه گذرای کرده و در صف قرار می‌دهیم.
5 Breadth First Search Step Five سپس گره مجاور بازدید نشده از S گره C است. آن را به عنوان بازدید شده نشانه‌گذاری کرده و در صف قرار می‌دهیم.
6 Breadth First Search Step Six اینک S گره مجاور بازدید نشده‌ای ندارد. بنابراین مقادیر آخر را از صف خارج کرده و رأس A را پیدا می‌کنیم.
7 Breadth First Search Step Seven از رأس A رأس D را به عنوان گره بازدید نشده مجاور داریم. آن را به صورت بازدید شده نشانه‌گذاری کرده و در صف قرار می‌دهیم.

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

پیاده‌سازی الگوریتم جستجوی سطح-اول در زبان C

در ادامه پیاده‌سازی کد C مثالی که در بخش قبلی بررسی کردیم را مشاهده می‌کنید.

اگر کد فوق را کامپایل و اجرا کنیم، نتیجه زیر حاصل می‌آید:

خروجی

Breadth First Search: S A B C D

بدین ترتیب این راهنما با موضوع معرفی گراف به عنوان یک ساختار داده و الگوریتم‌های مربوطه به پایان می‌رسد. هر گونه دیدگاه یا پیشنهاد خود را می‌توانید در بخش نظرات، در ادامه با ما و دیگر خوانندگان فرادرس در میان بگذارید.

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

==

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

نظر شما چیست؟

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