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

جستجوی اول عمق در جاوا (Depth First Search)

جستجوی اول عمق در جاوا

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

جستجوی اول عمق

در نظریه‌ گراف، جستجوی عمق اول یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار می‌رود.

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

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

پیاده سازی جستجوی اول عمق در جاوا

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

ابتدا کد جستجوی اول عمق در جاوا را ببینید سپس به توضیح آن و نحوه پیاده سازی آن خواهیم پرداخت.

public class DFS {
     private boolean[] marked;
     private int count;

     public DFS(Graph G, int s) {
          marked = new boolean[G.V()];
          dfs(G, s);
     }

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

              if (!marked[w]) {
                   dfs(G, w);
              }
          }
     }

     public boolean marked(int v) {
          return marked[v];
     }

     public int count() {
          return count;
     }


     public static void main(String[] args) {


          try {
              Graph g = new Graph(new File("graph.txt"));
              DFS dfs = new DFS(g, 0);
               for (int v = 0; v < g.V(); v++) {
               if (dfs.marked(v))
               System.out.print(v + " ");
               }
          } catch (FileNotFoundException e) {
              e.printStackTrace();
          }
     }
}

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

  1. Count: نگهداری تعداد راس های مجزایی که در جستجو آنها را ملاقات میکنیم.
  2. Marked: آرایه ای که هر اندیس آن نشان دهنده یک راس است و اگر marked[1] مقدارش برابر true باشد بدین معنی است که در جستجو این راس را ملاقات کردیم.

کد بالا همچنین شامل متدهای زیر است:

  1. Count: تعداد راس های ملاقات شده را به ما میدهد.
  2. Marked: به ما میگوید یک راس مشخص در جستجو ملاقات شده است یا خیر
  3. DFS: متد constructor ما است که شروع کننده جستجو است. به عنوان ورودی یک گراف و یک راس به عنوان ریشه میگیرد.
  4. dfs: متدی که جستجو انجام میدهد.
  5. Adj: همسایه های یک راس خاص را به ما میدهد(در رابطه برنامه نویسی گراف توضیح داده شده است)
  6. Main: کد تست جستجوی عمق اول در جاوا

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

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

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

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

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

0 1 2 3 4 5 6

برای ریشه 10 خروجی زیر را میگیریم

9 10 11 12

برای تغییر ریشه در main قسمت (DFS dfs = new DFS(g, 0 را با کد زیر تغییر دهید.

DFS dfs = new DFS(g, 10);

ریشه ما از 0 به 10 تغییر کرد.

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

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

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