{CodeGate}

گراف در سی شارپ (graph in csharp)

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

گراف در جاوا

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

گراف در جاوا

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

گراف در جاوا

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

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

گراف در جاوا

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

گراف در سی شارپ

حال به پیاده سازی گراف در سی شارپ میپردازیم. ابتدا یک کلاس به نام گراف(Graph) میسازیم. در این کلاس سه فیلد میسازیم:

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

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

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

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

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

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

 

پسورد: www.codegate.ir

دسته : #c, ساختمان داده در سی شارپ, گراف در سی شارپ

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

نظر شما چیست؟

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

wpDiscuz