جاوا

جلسه ۷۱: مرتب سازی توپولوژیکی گراف به روش بازگشتی در جاوا

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

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

مرتب سازی توپولوژیکی چیست؟

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

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

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

class TopologicalSortClass {

    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 4 ==> 2 -> 4
        public void addEgde(int fromNode, int toNode) {
            tempList[fromNode].addFirst(toNode);
        }
        
        public void topologicalSorting() {
            boolean[] visited = new boolean[numVertices];
            Stack ts = new Stack<>();
            
            //visit from each node if not already visited
            for (int i = 0; i < numVertices; i++) {
                if (!visited[i]) {
                    topologicalSortRecursive(i, visited, ts);
                }
            }
            System.out.println("Topological Sort: ");
            int size = ts.size();
            for (int i = 0; i < size; i++) {
                System.out.print(ts.pop() + " ");
            }
        }

        public void topologicalSortRecursive(int start, boolean[] visited, Stack ts) {
            visited[start] = true;
            for (int i = 0; i < tempList[start].size(); i++) {
                int vertex = tempList[start].get(i);
                if (!visited[vertex])
                    topologicalSortRecursive(vertex, visited, ts);
            }
            ts.push(start);
        }
        
    }

    public static void main( String args[] ) {
        System.out.println( "Path after Topological Sorting: " );

        int nVertices = 5;

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

        // Topological function called here
        g.topologicalSorting();

    }

}

تفسیر کد

کد بازگشتی را می توان به دو قسمت تقسیم کرد. اولی متد بازگشتی است و دومی متد main که متد بازگشتی اولین بار داخل آن فراخوانی می شود. قبل از بررسی متد topologicalSortRecursive ، جزئیات کلاس Graph را مرور کوتاهی می کنیم. کلاس Graph در خط ۴ و ۵ دارای دو متغیر است: numVertices که تعداد کل رئوس گراف را نشان می دهد و لیستی که شامل عناصری از نوع Integer است و tempList نامیده می شود. متد addEdge از خط ۱۷ تا ۱۹ دو گره را به عنوان آرگومان دریافت می کند و یک یال بین آنها ایجاد می کند. این کلاس همچنین از متدهای topologicalSorting و topologicalSortRecursive استفاده می کند ، که مرتب سازی توپولوژیکی را بر روی گراف اجرا می کند. در ادامه دو بخش کد را به صورت جداگانه بررسی می کنیم:

متد main

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

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

متد بازگشتی

اکنون که از نحوه فراخوانی کد بازگشتی مطلع شدیم ، جزئیات متدهای topologicalSorting و topologicalSortRecursive را بررسی می کنیم. این قسمت کد ، بین خطوط ۲۱ و ۴۶ در قطعه کد بالا است.

  • ()topologicalSorting برای مشخص کردن رئوس بازدید شده ابتدا یک نوع آرایه بولی با نام visited ایجاد می کند. و همچنین یک پشته جدید به نام stack ایجاد می کند.
  • حلقه for از خط ۲۶ تا خط ۳۰ تا زمانی که تمام رئوس ملاقات شوند ادامه می یابد. در صورتی که راسی ملاقات نشده باشد ، با فراخوانی متد اصلی topologicalSortRecursive آن را ملاقات می کند.
  • متد topologicalSortRecursive سه آرگمان می گیرد. اولین آرگمان (vertex) راسی است که باید ملاقات شود. آرگمان دوم (visited) رئوس ملاقات شده را مشخص می کند. آرگمان سوم پشته (stack) است.
  • این متد راس ابتدایی را می گیرد و پس از ملاقات آن روی رئوس مجاور این راس که ملاقات نشده اند فراخوانی بازگشتی به خودش انجام می دهد. این متد یکی از گره های فرزند را انتخاب می کند و سپس به سمت پایین حرکت می کند و گره فرزند ملاقات نشده آن راس را نیز ملاقات می کند. اگر متوجه شود که راس مجاوری وجود ندارد یا همه رئوس مجاور ملاقات شده اند ، این راس را روی پشته قرار می دهد و به سمت آخرین راس به بالا باز می گردد. در این فرایند بازگشت به بالا به هر راسی که می رسد رئوس مجاور آن را بررسی می کند که ملاقات شده باشند. پس از بررسی همه گره های مجاور ، همین چرخه دوباره ادامه می یابد.
  • حلقه for از خط ۳۱ تا ۳۵ رئوسی را که در طول topologicalSortRecursive در پشته قرار گرفته اند را چاپ می کند. این ما را قادر می سازد تا مسیر پیموده شده در مرتب سازی توپولوژیکی را مشاهده کنیم.

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

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

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

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

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

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