java, جاوا, گراف در جاوا

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

گراف در جاوا

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

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

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

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

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

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

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

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

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

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

   public Graph(int E) {
          this.E = E;
          adjance_list = new ArrayList[E+1];
     }

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

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

   public void add_vertex(int first_edge, int second_edge) {
          if (first_edge > E || first_edge < 0 || second_edge > E
                   || second_edge < 0) {
              return;
          }
          V_counter++;
          if (adjance_list[first_edge] != null) {
              adjance_list[first_edge].add(second_edge);
          } else {
              adjance_list[first_edge] = new ArrayList<>();
              adjance_list[first_edge].add(second_edge);
          }

          if (adjance_list[second_edge] != null) {
              adjance_list[second_edge].add(first_edge);
          } else {
              adjance_list[second_edge] = new ArrayList<>();
              adjance_list[second_edge].add(first_edge);
          }
}

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

public void printGraph() {
     for (int i = 0; i < adjance_list.length; i++) {
          if (adjance_list[i] != null) {
for (Iterator iterator = adjance_list[i].iterator(); iterator.hasNext();) {
Integer temp = (Integer) iterator.next();
                        System.out.println(i+" --> " + temp);

                   }
              }
          }
     }

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

 public static void main(String[] args) {
          Graph g = new Graph(5);
          g.add_vertex(1, 5);
          g.add_vertex(1, 4);
          g.add_vertex(1, 2);
          g.add_vertex(2, 3);
          g.add_vertex(3, 5);
          g.add_vertex(4, 5);
          g.printGraph();

     }

نوشته های مشابه

دیدگاهتان را بنویسید

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