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

مولفه همبندی در جاوا (Connected Component)

مولفه همبندی در جاوا

در این قسمت تیم کدگیت را با آموزش مولفه همبندی در جاوا (connected component)همراهی کنید. پیش نیاز این آموزش، آشنایی با جستجوی اول عمق و رابطه برنامه نویسی گراف و صف است.

مولفه همبندی (connected component)

در نظریه گراف، هر گراف ساده دارای یک یا بیشتر مولفه همبندی است. یک زیر گراف مانند H از G یک مولفه همبندی برای G است اگر و فقط اگر بین هر دو راس در H، دست‌کم یک مسیر وجود داشته باشد و با افزودن هر راس (و یا یال) دیگری از G به H  این خاصیت از بین برود. به عبارت دیگر هر زیر گراف بیشینه و همبند از G، یک مولفه همبندی G است.

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

برای پیدا کردن مولفه‌های همبندی یک گراف، (G(V,E، نیاز به زمان اجرای خطی نسبت به طول ورودی (|O(|E| + |V داریم.(ویکیپدیا)

مولفه همبندی در جاوا

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

import java.io.File;
import java.io.FileNotFoundException;

public class CC {

     private boolean[] marked;
     private int[] id;
     private int[] size;
     private int count;


     public CC(Graph G) {
          marked = new boolean[G.V()];
          id = new int[G.V()];
          size = new int[G.V()];
          for (int v = 0; v < G.V(); v++) {
              if (!marked[v]) {
                   dfs(G, v);
                   count++;
              }
          }
     }

     private void dfs(Graph G, int v) {
          marked[v] = true;
          id[v] = count;
          size[count]++;
          for (int w : G.adj(v)) {
              if (!marked[w]) {
                   dfs(G, w);
              }
          }
     }


     public int id(int v) {
          return id[v];
     }


     public int size(int v) {
          return size[id[v]];
     }


     public int count() {
          return count;
     }


     public boolean areConnected(int v, int w) {
          return id(v) == id(w);
     }


}

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

  1. Marked: آرایه ای به تعداد راس های ما است و اگر راسی را ملاقات کنیم مقدار اندیس آن راس در آرایه marked میشود true (یعنی اگر راس 3 را ملاقات کنیم مقدار marked[3]=true میشود).
  2. Id: هر مولفه همبندی یک شناسه دارد. آرایه id شناسه مولفه همبندی هر راس را در خود نگه میدارد(اگر راس 3 در مولفه همبندی شماره 5 قرار دارد مقدار id[3]=5 میشود).
  3. Size: آرایه size تعداد راسهای درون مولفه همبندی خاص را به ما میدهد.
  4. Count: متغیر count تعداد کل مولفه همبندی در گراف ما را میدهد.

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

  1. Id: شناسه راس ورودی را به ما میدهد.
  2. Count: تعداد کل مولفه های همبندی گراف را به ما میدهد.
  3. Size: تعداد راس های درون مولفه همبندی که راس ورودی در آن قرار دارد را به ما میدهد.
  4. areConnected: بررسی میکند که دو راس خاص به هم مسیری دارند(درون یک مولفه همبندی خاص هستند ).
  5. Dfs: جستجوی اول عمق(در آموزش های گذشته توضیح داده شده است)
  6. CC: متد constructor کلاس ما است. و در این متد شروع به پیدا کردن مولفه های همبندی مختلف میکنیم با استفاده از جستجوی اول عمق.

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

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

     public static void main(String[] args) {
          Graph G = null;
          try {
              G = new Graph(new File("tinyG.txt"));
          } catch (FileNotFoundException e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
          }
          CC cc = new CC(G);

          // number of connected components
          int M = cc.count();
          System.out.println(M + " components");

          // compute list of vertices in each connected component
          Queue<Integer>[] components = (Queue<Integer>[]) new Queue[M];

          for (int i = 0; i < M; i++) {
              components[i] = new Queue<Integer>();
          }
          for (int v = 0; v < G.V(); v++) {
              components[cc.id(v)].Enqueue(v);
          }

          // print results
          for (int i = 0; i < M; i++) {
              components[i].print();
          }

     }

در کد بالا ما یک گراف ساختیم و مولفه های همبندی مختلف آن را پیدا کردیم و آن ها را به صورت جداگانه چاپ کردیم.

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

خروجی مولفه همبندی در جاوا

خروجی کد بالا به صورت زیر است

3 components
0 1 2 3 4 5 6
7 8
9 10 11 12

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

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

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