تنفيذ أسلوب البحث بالعمق أولاً باستخدام طريقتي التعاود والتكرار في جافا

تُعتبر خوارزمية البحث بالعمق أولاً (Depth-First Search – DFS) واحدة من أهم خوارزميات البحث والتنقيب في علوم الحاسوب، وتستخدم بشكل واسع في استكشاف الهياكل البيانية مثل الأشجار والرسوم البيانية (Graphs). يتميز هذا الأسلوب بقدرته على الغوص عميقاً داخل مسار معين من العقد قبل التراجع والبحث في المسارات الأخرى، مما يجعله ملائماً لمشاكل عديدة مثل إيجاد المسارات، فحص الترابط، أو التحقق من وجود دوائر.

في هذا المقال سنستعرض شرحاً موسعاً لأسلوب البحث بالعمق أولاً مع التركيز على تنفيذه بلغة جافا عبر طريقتين أساسيتين: الطريقة التكرارية (Iterative) وطريقة التعاود (Recursive). كما سنتناول مميزات وعيوب كل طريقة، بالإضافة إلى تحليل للأداء العملي في كل منهما، مع شرح تفصيلي للشفرة المصدرية وطريقة عملها.

مفهوم البحث بالعمق أولاً (DFS)

البحث بالعمق أولاً هو أسلوب يعتمد على استكشاف العقد في الرسم البياني أو الشجرة بأعمق نقطة ممكنة قبل الرجوع والتراجع لاستكشاف المسارات البديلة. يبدأ البحث من عقدة بداية محددة، ثم يتبع مساراً حتى يصل إلى نهاية المسار أو نقطة لا يمكن الاستمرار منها، عندها يرجع خطوة للوراء ليستكشف المسارات الأخرى.

بمعنى آخر، يقوم DFS بالغطس في عمق الرسم البياني بطريقة منظمة، ويستمر في النزول من عقدة إلى أخرى عبر الحواف حتى لا تتوفر خيارات أخرى، ثم يتراجع إلى العقد السابقة ليبدأ استكشاف مسارات أخرى.

لماذا نستخدم البحث بالعمق أولاً؟

تستخدم DFS في العديد من التطبيقات نظراً لميزاتها الفريدة، منها:

• اكتشاف مسارات: يمكن من خلالها إيجاد طريق من عقدة بداية إلى عقدة هدف.

• فحص الترابط: تساعد في تحديد ما إذا كان الرسم البياني متصلًا (Connected).

• الكشف عن الدوائر: تُمكن من اكتشاف وجود دوائر (Cycles) في الرسم البياني.

• ترتيب طوبولوجي: تستخدم DFS في الترتيب الطوبولوجي للرسوم البيانية الموجهة.

• حل مسائل الألعاب والمتاهات: عن طريق استكشاف المسارات المحتملة.

طرق تنفيذ البحث بالعمق أولاً في جافا

تنقسم طرق تنفيذ DFS عادة إلى نوعين رئيسيين:

1. طريقة التعاود (Recursive)

تعتمد على استدعاء الدالة نفسها ضمنياً لتنفيذ عملية البحث في كل عقدة متجاورة. هي الطريقة الأكثر طبيعية وأسهل للفهم والتنفيذ في معظم الحالات.

2. الطريقة التكرارية (Iterative)

تستخدم هياكل بيانات مثل المكدس (Stack) لمحاكاة عملية التعمق بدون الحاجة إلى الاستدعاء الذاتي. هذه الطريقة مفيدة لتجنب مشكلة تجاوز حدود الذاكرة التي قد تحدث في الاستدعاء التعاودي خاصة مع الرسوم البيانية الكبيرة.

تمثيل الرسم البياني في جافا

قبل البدء في شرح الطرق، من الضروري توضيح كيفية تمثيل الرسم البياني (Graph) في جافا. هناك أكثر من طريقة، لكن الأكثر شيوعاً هي استخدام قائمة الجوار (Adjacency List) لأنها فعالة في الذاكرة وتسمح بتمثيل الرسوم البيانية المتفرعة والمتصلة بسهولة.

java
CopyEdit
import java.util.*;

public class Graph {
    private int V; // عدد العقد (Vertices)
    private LinkedList adj[]; // قائمة الجوار

    // منشئ الرسم البياني
    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for(int i=0; inew LinkedList<>();
    }

    // إضافة حافة بين عقدتين
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
}

بهذا الشكل، يتم تمثيل الرسم البياني كمصفوفة من القوائم المرتبطة، حيث تمثل كل قائمة الجوار العقد المرتبطة بالعقدة المعنية.

1. طريقة التعاود (Recursive DFS)

الفكرة العامة

في طريقة التعاود، يتم البدء من عقدة معينة، ثم نعلم هذه العقدة كمزارة (زيارة) لمنع الدخول المتكرر، بعدها نستدعي دالة DFS بشكل متكرر على جميع العقد المجاورة غير المزارة. تتكرر هذه العملية حتى يتم زيارة جميع العقد الممكنة من نقطة البداية.

الشفرة البرمجية

java
CopyEdit
public class Graph {
    private int V;
    private LinkedList adj[];

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for(int i=0; inew LinkedList<>();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // دالة مساعدة لتنفيذ DFS باستخدام التعاود
    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        // استكشاف كل الجيران غير المزارة
        for (int n : adj[v]) {
            if (!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }

    // دالة بدء البحث
    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }
}

شرح التنفيذ

• المصفوفة visited: تستخدم لتتبع العقد التي تم زيارتها.

• عند زيارة عقدة، يتم طباعتها أو تنفيذ العملية المطلوبة.

• تتم استدعاءات متكررة للدالة نفسها لكل جارة غير مزارة.

• عملية التكرار تنتهي عندما يتم زيارة كل العقد الممكن الوصول إليها من نقطة البداية.

مميزات طريقة التعاود

• بساطة وسهولة في الفهم والكتابة.

• الكود أكثر وضوحاً ويشبه التعبير الرياضي.

• مناسِبة للرسوم البيانية ذات العمق المحدود.

عيوب طريقة التعاود

• قد تسبب مشاكل تجاوز مكدس الاستدعاءات (Stack Overflow) مع الرسوم البيانية العميقة جداً.

• الأداء محدود بعمق الاستدعاءات.

2. الطريقة التكرارية (Iterative DFS)

الفكرة العامة

في الطريقة التكرارية، يتم استخدام مكدس (Stack) لتتبع العقد التي يجب زيارتها. تبدأ بوضع العقدة البداية في المكدس، ثم:

• استخراج العقدة من المكدس.

• إذا لم تُزر من قبل، يتم وسمها كمزارة وتنفيذ العملية (مثل الطباعة).

• إضافة جميع جيرانها غير المزارة إلى المكدس.

• تكرار الخطوات حتى يصبح المكدس فارغًا.

الشفرة البرمجية

java
CopyEdit
import java.util.*;

public class Graph {
    private int V;
    private LinkedList adj[];

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for(int i=0; inew LinkedList<>();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSIterative(int s) {
        boolean visited[] = new boolean[V];
        Stack stack = new Stack<>();

        stack.push(s);

        while(!stack.isEmpty()) {
            int v = stack.pop();

            if(!visited[v]) {
                System.out.print(v + " ");
                visited[v] = true;
            }

            // إضافة الجيران غير المزارة إلى المكدس
            for(int n : adj[v]) {
                if(!visited[n]) {
                    stack.push(n);
                }
            }
        }
    }
}

شرح التنفيذ

• تبدأ من العقدة s وتُضاف إلى المكدس.

• بينما المكدس ليس فارغاً، تستخرج عقدة وتزور إذا لم تُزر من قبل.

• تضيف جيران العقدة المستخرجة إلى المكدس للاستكشاف لاحقاً.

• تستمر العملية حتى زيارة كل العقد الممكنة.

مميزات الطريقة التكرارية

• تتجنب مشاكل تجاوز مكدس الاستدعاءات.

• أكثر أماناً عند العمل مع رسوم بيانية عميقة أو ضخمة.

• يمكن التحكم بوضوح في كيفية إدارة الذاكرة.

عيوب الطريقة التكرارية

• الشفرة قد تكون أكثر تعقيدًا مقارنة بالطريقة التعاودية.

• إدارة المكدس يدوياً قد يزيد من التعقيد في بعض الحالات.

مقارنة بين طريقتي التعاود والتكرار

تحسينات وتوسعات ممكنة على DFS

1. البحث متعدد الاتجاهات (Bidirectional DFS)

يتم البحث من نقطتي بداية ونهاية في نفس الوقت للعثور على المسار بشكل أسرع.

2. حفظ المسارات

يمكن تعديل DFS ليحفظ المسار الكامل الذي يمر به، وليس فقط العقد التي تم زيارتها.

3. استخدام DFS في الرسوم البيانية غير الموجهة والموجهة

تختلف معالجة الحواف في الرسوم البيانية الموجهة عن غير الموجهة أثناء DFS، خاصة في كشف الدورات.

4. استخدام DFS في تحليل المكونات المتصلة (Connected Components)

يمكن تطبيق DFS لاستكشاف كل مكونات الرسم البياني المتصلة وتعدادها.

تطبيق عملي كامل مع مثال

لإظهار قوة ومرونة خوارزمية DFS، نقدم المثال التالي الذي ينشئ رسماً بيانياً موجهًا، ويطبق DFS بالطريقتين، مع عرض النتائج.

java
CopyEdit
public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 4);
        g.addEdge(3, 5);
        g.addEdge(4, 5);

        System.out.println("DFS باستخدام التعاود:");
        g.DFS(0);

        System.out.println("\n\nDFS باستخدام التكرار:");
        g.DFSIterative(0);
    }
}

النتائج المتوقعة:

nginx
CopyEdit
DFS باستخدام التعاود:
0 1 3 5 4 2

DFS باستخدام التكرار:
0 2 4 5 1 3

يرجى ملاحظة أن ترتيب الزيارة قد يختلف قليلاً حسب كيفية ترتيب إضافة الجيران إلى المكدس في الطريقة التكرارية، إلا أن كلا الطريقتين تقومان بزيارة جميع العقد الممكنة.

تحليل تعقيد خوارزمية البحث بالعمق أولاً

• الزمن:
  
  تعتمد خوارزمية DFS على عدد العقد (V) وعدد الحواف (E) في الرسم البياني. في أسوأ الحالات، تتم زيارة كل عقدة وكل حافة مرة واحدة، لذا يكون التعقيد الزمني:
  
  O(V + E)

• المساحة:
  
  تستهلك خوارزمية DFS مساحة ذاكرة لتخزين معلومات الزيارة (visited) والمكدس أو مكدس الاستدعاءات. في أسوأ الحالات (رسم بياني خطي)، قد تصل مساحة المكدس إلى عمق الرسم البياني، أي:
  
  O(V)

جدول مقارنة مختصر بين طرق تنفيذ DFS

الخلاصة

تُعد خوارزمية البحث بالعمق أولاً من الركائز الأساسية في مجال البرمجة والخوارزميات، وتفهم طرق تنفيذها بلغة جافا من خلال طريقتي التعاود والتكرار يُمكن المطورين من اختيار الأسلوب الأنسب لمتطلبات التطبيق وحجم البيانات. الطريقة التعاودية تتميز بسهولة ووضوح الكود لكنها قد تواجه مشاكل في الرسوم البيانية العميقة، بينما توفر الطريقة التكرارية تحكماً أكبر وتجنباً لمشاكل استهلاك مكدس الاستدعاءات، لكنها تحتاج إلى إدارة يدوية للمكدس.

من المهم عند تنفيذ DFS مراعاة طبيعة الرسم البياني وحجم البيانات، بالإضافة إلى استخدام البُنى المناسبة مثل قائمة الجوار لضمان أداء وفعالية الخوارزمية.

المصادر والمراجع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition, The MIT Press, 2009.

• GeeksforGeeks, Depth First Search or DFS for a Graph, https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

بهذا المقال تم تقديم شرح متكامل وعميق حول كيفية تنفيذ خوارزمية البحث بالعمق أولاً في لغة جافا باستخدام الطريقتين التعاودية والتكرارية مع التحليل والمقارنة، مما يعزز الفهم العميق لهذه الخوارزمية الحيوية في علوم الحاسوب.