{CodeGate}

گراف در جاوا (Graph implementation)

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

گراف در جاوا

 برای پیاده سازی گراف در جاوا روش هایی مثل آرایه توصیه می‌شود. مثلا یک آرایه دو بعدی بسازیم که تعداد سطر و ستون آن برابر راس باشد. حال اگر راس 1 به راس 5 یالی داشته باشد خانه 1و5 (در آرایه میشود 0و4) را 1 میگذاریم بدین معنی که این دو خانه به هم یالی دارند.

گراف در جاوا

روش بالا را ماتریس مجاورت میگویند. این روش توصیه  نمیشود به دلیل فضای زیادی که از حافظه میگیرد.روش دوم استفاده لیستی است که فقط همسایه های یک راس در آن نگه داشته می شود(لیست همسایگی).همانند شکل زیر

گراف در جاوا

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

ایده پیاده سازی لیست همسایگی در جاوا به شکل زیر است

گراف در جاوا

بدین صورت که ما یک آرایه از arraylist داریم!!! طول آرایه برابر با تعداد راس ها است. به عنوان مثال اگر بخواهیم بگوییم راس های 1 و 2 یک یال متصل به هم دارند به خانه 1 آرایه رجوع میکنیم و به لیست آن عدد 2 اضافه و به خانه 2 آرایه رجوع و به لیست آن خانه عدد یک را اضافه میکنیم.(اگر کمی گیج کننده است مشکلی نیس داخل کد بهتر متوجه می شوید!!!)

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

گراف در جاوا

در این کلاس سه فیلد به نام

  • V_counter(شمارنده تعداد یال های گراف)
  • E(تعداد راسهای گراف)
  • adjance_list(لیست همسایگی)

در constructor کلاس گراف تعداد راس ها را میگیریم و لیست همسایگی را میسازیم به صورت زیر:

دلیل ساختن آرایه به طول E+1  آن است که آرایه از صفر شروع میشود.

حال متدی به نام add_vertex مینویسیم. کار این متد این است که دو خانه ای که همسایه هستند را به عنوان ورودی بگیرد و در لیست همسایگی قرار دهد.

در آخر هم متدی برای نمایش دادن گراف مینویسیم.

در آخر برای برنامه main مینویسیم.

 

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

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

نظر شما چیست؟

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

wpDiscuz