تنفيذ أسلوب البحث بالعمق أولاً باستخدام الواجهتين Iterable و Iterator

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

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

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

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

يُستخدم DFS في مجموعة واسعة من التطبيقات، مثل:

• التحقق من وجود مسار بين عقدتين في الرسم البياني.

• إيجاد المكونات المترابطة (Connected Components).

• اكتشاف الدورات (Cycles) في الرسم البياني.

• توليد حلول المسائل التي تعتمد على البحث في كل المسارات (كحل الألغاز، الألعاب).

واجهة Iterable و Iterator: التعريف والدور

واجهة Iterable

تعتبر واجهة Iterable هي العقدة الأساسية التي تدل على إمكانية التكرار (Iteration) عبر مجموعة من العناصر. أي كائن (Object) ينفذ هذه الواجهة يمكن أن يُستخدم في الحلقات التكرارية (مثل for-each في جافا)، حيث تعبر هذه الواجهة عن قابلية الكائن للتمرير عبر عناصره بشكل متتابع.

في جافا، تحتوي واجهة Iterable على دالة رئيسية واحدة وهي:

java
CopyEdit
Iterator iterator();

تقوم هذه الدالة بإرجاع كائن Iterator، الذي يتحكم في عملية المرور على العناصر.

واجهة Iterator

واجهة Iterator تتيح المرور على عناصر مجموعة معينة بشكل متتابع. تشمل هذه الواجهة ثلاث وظائف رئيسية:

• boolean hasNext(): تتحقق مما إذا كان هناك عنصر آخر متاح للقراءة.

• T next(): تعيد العنصر التالي في التتابع.

• void remove(): تحذف العنصر الذي تم تمريره مؤخراً (هذه العملية اختيارية وغالباً ما لا تُستخدم).

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

لماذا استخدام Iterable و Iterator في تنفيذ DFS؟

السبب الأساسي لاستخدام هاتين الواجهتين في تنفيذ DFS يعود إلى الحاجة إلى تجريد عملية التكرار بحيث تصبح مرنة وقابلة لإعادة الاستخدام في سياقات مختلفة. عند تصميم خوارزمية DFS باستخدام Iterable و Iterator، يمكن للمستخدمين أو المطورين التعامل مع هياكل بيانات معقدة دون الحاجة لمعرفة التفاصيل الداخلية للهيكل.

هذا النهج يعزز من مبدأ الانعزال (Abstraction) في البرمجة، ويساعد على بناء أنظمة أكثر تنظيماً وسهولة في الصيانة، بالإضافة إلى القدرة على استبدال أو تعديل الخوارزميات بدون تأثير كبير على باقي أجزاء البرنامج.

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

1. تعريف هيكل البيانات

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

مثال على ذلك في جافا:

java
CopyEdit
import java.util.*;

class Node {
    T value;
    List> neighbors;

    Node(T value) {
        this.value = value;
        this.neighbors = new ArrayList<>();
    }

    void addNeighbor(Node neighbor) {
        neighbors.add(neighbor);
    }

    List> getNeighbors() {
        return neighbors;
    }
}

2. إنشاء DFS Iterator

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

java
CopyEdit
class DFSIterator implements Iterator> {
    private Stack> stack = new Stack<>();
    private Set> visited = new HashSet<>();

    DFSIterator(Node start) {
        stack.push(start);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public Node next() {
        if (!hasNext()) throw new NoSuchElementException();

        Node current = stack.pop();
        visited.add(current);

        for (Node neighbor : current.getNeighbors()) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
        return current;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

3. إنشاء DFS Iterable

لكي يمكن استخدام DFS بسهولة مع حلقات for-each أو مع أي كود يستفيد من Iterable، يتم إنشاء فصل (class) ينفذ Iterable ويعيد Iterator الخاص بالبحث بالعمق أولاً.

java
CopyEdit
class DFSIterable implements Iterable> {
    private Node start;

    DFSIterable(Node start) {
        this.start = start;
    }

    @Override
    public Iterator> iterator() {
        return new DFSIterator<>(start);
    }
}

4. استخدام DFS

بعد بناء هذه الهياكل، يمكن للمبرمجين استخدام البحث بالعمق أولاً بشكل بسيط ومرن:

java
CopyEdit
public class Main {
    public static void main(String[] args) {
        Node nodeA = new Node<>("A");
        Node nodeB = new Node<>("B");
        Node nodeC = new Node<>("C");
        Node nodeD = new Node<>("D");
        Node nodeE = new Node<>("E");

        nodeA.addNeighbor(nodeB);
        nodeA.addNeighbor(nodeC);
        nodeB.addNeighbor(nodeD);
        nodeC.addNeighbor(nodeE);

        DFSIterable dfsIterable = new DFSIterable<>(nodeA);

        for (Node node : dfsIterable) {
            System.out.println(node.value);
        }
    }
}

في هذا المثال، يبدأ البحث من العقدة A، ثم يستكشف أعمق المسارات الممكنة قبل التراجع إلى العقد الأخرى.

مميزات وخصائص تنفيذ DFS باستخدام Iterable و Iterator

• سهولة الاستخدام: يمكن استخدام حلقة for-each مع الكائنات التي تنفذ Iterable، مما يبسط الكود.

• تجريد العملية: تم فصل منطق التكرار (iteration) من منطق هيكل البيانات، مما يجعل الكود أكثر مرونة وقابلية لإعادة الاستخدام.

• إدارة الذاكرة: استخدام المكدس المدمج في Iterator للتحكم في الترتيب الذي يتم به زيارة العقد.

• التحكم في التكرار: بفضل واجهة Iterator يمكن إيقاف التكرار أو التحكم فيه بطريقة دقيقة.

التعامل مع الدورات في الرسوم البيانية

من أهم التحديات التي تواجه تطبيق DFS هو التعامل مع الرسوم البيانية التي تحتوي على دورات، حيث يمكن أن يتسبب ذلك في زيارة العقد نفسها عدة مرات مما يؤدي إلى حلقات لا نهائية. في الكود السابق تم استخدام مجموعة visited (مجموعة من العقد التي تمت زيارتها) لمنع إعادة زيارة العقد.

هذا الأسلوب يضمن أن الخوارزمية تنهي عملها بشكل صحيح حتى مع وجود دورات في الرسم البياني.

تحسينات وإضافات ممكنة

1. تنفيذ DFS مع استدعاء دالة رد نداء (Callback Function): يمكن تعديل Iterator أو Iterable لقبول دالة يتم تنفيذها عند زيارة كل عقدة، مما يزيد من مرونة الاستخدام.

2. تنفيذ DFS متوازٍ (Parallel DFS): في حالات معينة يمكن توزيع البحث عبر خيوط متعددة لتحسين الأداء في الرسوم البيانية الكبيرة.

3. تخصيص الأولوية في الزيارة: عن طريق تعديل ترتيب إضافة العقد إلى المكدس يمكن التحكم في أولوية الاستكشاف.

4. تضمين خيارات للبحث المحدود العمق (Depth-Limited Search): يمكن إضافة متغير يعبر عن أقصى عمق مسموح به للبحث لمنع البحث في مسارات طويلة جداً.

مقارنة بين استخدام DFS مع Iterable و Iterator وبين الطرق التقليدية

الطرق التقليدية لتنفيذ DFS تعتمد غالباً على كتابة دوال استعادية (recursive) أو كتابة خوارزمية مخصصة لا تتبع مفهوم التكرار القياسي. في المقابل، تنفيذ DFS عبر Iterable و Iterator يقدم:

• واجهة برمجية موحدة يمكن استخدامها مع هياكل بيانات متعددة.

• القدرة على دمج البحث بسهولة مع بنيات أخرى تعتمد على التكرار.

• زيادة وضوح الكود وتقليل احتمالية الخطأ في إدارة الحالة.

• دعم أفضل لأنماط البرمجة التفاعلية والحديثة.

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

خلاصة

تنفيذ أسلوب البحث بالعمق أولاً باستخدام واجهتي Iterable و Iterator يمثل طريقة فعالة ومرنة لتنفيذ خوارزمية DFS بطريقة منظمة ومجردة من التفاصيل الداخلية لهياكل البيانات. هذا النهج يعزز من قابلية صيانة الكود، يسهل دمجه مع أنماط برمجة حديثة، ويضمن إدارة سليمة للحالة أثناء البحث. كما يوفر تحكماً أفضل في عملية التكرار ويعزز قابلية الاستخدام عبر تطبيقات متعددة.

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

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

المراجع

1. Robert Sedgewick, Kevin Wayne, “Algorithms, 4th Edition”, 2011.

2. Joshua Bloch, “Effective Java”, 3rd Edition, Addison-Wesley, 2017.