رابط برنامه نویسی گراف جهت دار (Directed Graph Api)

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

  1. آشنایی با گراف
  2. آشنایی با لیست پیوندی در جاوا
  3. Iterator در جاوا
  4. آشنایی با واژه رابطه برنامه نویسی(منظور api است)
  5. آشنایی با This در جاوا
  6. آشنایی با Constructor در جاوا
  7. آشنایی با متد در جاوا
  8. آشنایی با آرایه
  9. آشنایی با خواندن و نوشتن فایل در جاوا
  10. حلقه while در جاوا
  11. آشنایی مدیریت استثناها
  12. آشنایی با if
  13. آشنایی به for
  14. آشنایی با شی گرایی

گراف جهت دار

تعریف زیر در سایت ویکیپدیا آمده است:

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

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

رابط برنامه نویسی گراف جهت دار

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

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

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

کد کلاس Bag

کد کلاس Node

کد کلاس listIterator

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

رابط برنامه نویسی گراف جهت دار

برای پیاده سازی رابط برنامه نویسی گراف جهت دار ابتدا باید آرایه ای از راس ها را داشته باشیم و در هر راس همسایه های آن را ذخیره کنیم. برای این کار ما راس ها را به صورت 0،1،2،….1-V نامگذاری کردیم پس مثلا اگر بگوییم راس 1 و 4 با هم همسایه هستند پس ما به اندیس 1 آرایه رئوس میرویم و عدد 4 را به همسایه های آن اضاف میکنیم.

کد گراف جهت دار

کد رابط برنامه نویسی گراف جهت دار که در بالا زده شده شامل متدهای زیر است:

  1. Adj : متدی که لیست همسایه های راس مشخصی را به میدهد.
  2. addEdge : متدی که دو راس در ورودی میگیرد(v و w) و راس v را به w متصل میکند.
  3. E : متدی که تعدار یال را به ما میدهد.
  4. V : متدی که تعداد راس ها را به ما میدهد.
  5. Reverse: متدی که جهت یال های گراف را برعکس میکند
  6. toString: نمایش کل گراف به صورت راس به راس.
  7. Digraph : متد constructor است. ما دو constructor داریم. اولی فقط یک تعداد راس ورودی میگیرد و گراف خالی تحویل میدهد.  دومی فایلی از گراف میگیرد که در آن فایل، راس های متصل به هم نشان داده شده است.

در کد رابط برنامه نویسی گراف جهت دار از سه فیلد استفاده شده است:

  1. E : متغییری که تعداد یال ها را نگه میدارد.
  2. V : متغییری که تعداد راس ها را نگه میدارد.
  3. Bag : آرایه ای از کلاس bag که لیست همسایه های هر راس به صورت جداگانه در آن نگهداری میشود. بدین معنی که در آرایه هر اندیس یک راس از گراف هست و لیستی از همسایه ها در خود نگه میدارد.

برای تست برنامه کد main زیر را بزنید.

در کد رابط برنامه نویسی گراف جهت دار ما از یک فایل (graph.txt) استفاده کردیم که گراف و راس هایی که میخواهیم در آن است. فایل به صورت زیر است:

سطر اول تعداد راس ها و سطر دوم تعداد یال ها است. سطر سوم به بعد راس هایی که به هم یال دارند نوشته شده است. به طور مثال  راس 4 و 2 به هم متصل هستند بدین معنی که از راس 4 به راس 2 یالی وجود دارد و نه برعکس(گراف جهت دار است).

پسورد: www.codegate.ir

دسته : java, جاوا, ساختمان داده در جاوا, گراف در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz