جاوا

جلسه ۷۰: جستجوی اول عمق در گراف ها به روش بازگشتی در جاوا

این جلسه نحوه نوشتن کد بازگشتی برای جستجوی اول عمق (Depth First Search یا DFS) در گراف ها را به شما آموزش می دهد. موارد زیر را بیان خواهیم کرد:

  • جستجوی اول عمق چیست؟
  • پیاده سازی به وسیله کد
  • تفسیر کد
  • متد main
  • متد بازگشتی
  • حالت بازگشتی
  • درک از طریق پشته

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

جستجوی اول عمق (Depth First Search یا DFS) روشی برای پیمایش و جستجوی همه گره های گراف است. این الگوریتم به ما اجازه می دهد تا مشخص کنیم بین دو گره a و b مسیری وجود دارد یا خیر. این فرایند از گره ریشه شروع می شود از طریق یال ها پیش می رود تا زمانی که به برگ (گره بدون فرزند) برسد ، و سپس مسیر را برمی گردد. این کار تا زمانی که از همه گره ها عبور کند، ادامه می یابد. تصویر زیر روند DFS را در یک گراف جهت دار نشان می دهد.

پیاده سازی به وسیله کد

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

class ExampleClass {

    static class Graph {
        int numVertices;
        LinkedList[] tempList;

        Graph(int numVertices) {
            this.numVertices = numVertices;
            tempList = new LinkedList[numVertices];
            for (int i = 0; i < numVertices ; i++) {
                tempList[i] = new LinkedList<>();
            }
        } 

        // Method to add an edge between 2 nodes in the Graph
        // fromNode 2 toNode 5 ==> 2 -> 5
        public void addEgde(int fromNode, int toNode) {
            tempList[fromNode].addFirst(toNode);
        }

        public void DFSRecursion(int startVertex) {
            boolean[] visitedArr = new boolean[numVertices];
            dfs(startVertex, visitedArr);
        }

        // DFS Recursion takes place here
        public void dfs(int start, boolean [] visitedArr) {
            visitedArr[start] = true;

            System.out.print(start + " ");

            for (int i = 0; i < tempList[start].size(); i++) {
                int toNode = tempList[start].get(i);
                if (!visitedArr[toNode])
                    dfs(toNode,visitedArr);
            }
        }
    }

    public static void main( String args[] ) {
        System.out.println( "Your DFS path is: " );

        int nVertices = 6;

        Graph g = new Graph(nVertices);
        
        g.addEgde(0, 1);
        g.addEgde(0, 2);
        g.addEgde(1, 3);
        g.addEgde(1, 4);
        g.addEgde(2, 5);

        // Root node given as argument to the function
        g.DFSRecursion(0);
    }
}

تفسیر کد

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

کد بازگشتی را می توان به دو قسمت تقسیم کرد. اولی متد بازگشتی است و دومی متد main که فراخوانی متد بازگشتی از آن شروع می شود. قبل از بررسی عملکرد واقعی متد dfs ، برخی از جزئیات کلاس Graph را مرور سریعی می کنیم.

  • کلاس Graph از خطوط ۳ تا ۱۳ دارای دو متغیر است. numVertices که تعداد کل رئوس گراف را نشان می دهد و لیستی شامل عناصری از نوع Integer است که thetempList نام دارد. متد addEdge از خط ۱۷ تا ۱۹ دو گره را به عنوان آرگومان دریافت می کند و یک یال بین آنها ایجاد می کند. این کلاس همچنین دارای متدهای DFSRecursion و dfs است که جستجوی اول عمق را روی گراف اجرا می کند.

حال بیایید به دو بخش کد نگاهی بیندازیم.

متد main

در این بخش، متد main را بررسی می کنیم که کد بازگشتی را فراخوانی می کند.

  • در متد main ، در خط ۴۳ ، متغیر nVertices مقدار دهی می شود. این متغیر تعداد رئوس نمودار را مشخص می کند.
  • در خط ۴۵ ، گراف جدیدی با تعداد رئوس nVertices ایجاد می شود.
  • از خطوط ۴۷ تا ۵۱ ، چندین یال ایجاد می شود که هر یال ۲ عدد صحیح را می گیرد ، مثلاً اگر آرگمان fromNode برابر ۲ و آرگمان toNode برابر ۵ باشد، یالی از گره ۲ به گره ۵ افزوده می شود.
  • در خط ۵۴ ، متد بازگشتی DFSRecursion با یک گره ریشه به عنوان آرگومان فراخوانی می شود.

متد بازگشتی

اکنون که توضیح دادیم چگونه متد بازگشتی فراخوانی می شود ، DFSRecursion و dfs را با جزئیات بررسی می کنیم. این قسمت کد از خطوط ۲۱ تا ۳۷ در قطعه کد بالا است. بررسی را از متد DFSRecursion شروع می کنیم که رأس ریشه را به عنوان آرگومان می گیرد و آرایه ای بولی به نام visitedArr ایجاد می کند. این آرایه رئوس ملاقات شده را مشخص می کند. پس از ایجاد این آرایه بولی ، متد اصلی بازگشتی یعنی متد dfs فراخوانی می شود. متد dfs دو آرگومان دریافت می کند ، راس startVertex که باید ملاقات شود به عنوان آرگومان اول و visitedArr که رئوس ملاقات شده را مشخص می کند به عنوان آرگومان دوم. در خط ۲۸ ، متد dfs ابتدا رأسی را که ملاقات شده به عنوان true در آرایه visitedArr مشخص می کند. این کار برای حفظ وضعیت ملاقات رئوس است. خط ۳۰ سپس شماره راس ملاقات شده را در کنسول چاپ می کند.

حالت بازگشتی

  • خطوط ۳۲ تا ۳۶ در یک حلقه for ، لیست tempList که شامل تمامی رئوس گراف است را پیمایش می کند.
  • شرط if در خط ۳۴ بیان می کند که اگر گره مقصد toNode بازدید نشده باشد ، باید متد dfs با پارامترهای جدید فراخوانی شود. در این فراخوانی راس شروع پیمایش راس toNode می باشد.
  • اما اگر شرط بالا برآورده نشود ، حلقه تا رسیدن به انتهای یال ها ادامه می یابد.

درک از طریق پشته

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

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

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

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

دکمه بازگشت به بالا