خوارزمية البحث الأول بالعمق (BFS): دليل شامل لاجتياز الرسوم البيانية مع أمثلة من Leetcode

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

ما هو البحث الأول بالعمق (BFS)؟

نعلم جميعًا أن الرسم البياني هو مجموعة من الرؤوس والحواف، ويُرمز له بالصيغة: G={V,E}. اجتياز الرسم البياني يعني زيارة كل رأس وكل حافة مرة واحدة بالضبط بطريقة منظمة. في خوارزمية BFS، يُطلب منا اجتياز الرسم البياني بعرضه أو مستوى تلو الآخر. هذا يعني أننا سنتحرك أفقيًا أولاً ونزور جميع العقد في الطبقة الحالية قبل الانتقال إلى الطبقة التالية. لذلك، كلما طُلب منا إجراء اجتياز بترتيب المستوى (level order traversal)، يمكننا استخدام تقنية BFS.

في BFS، نبدأ الاجتياز من العقدة 1 (العقدة الجذرية) ونزور عقدها الفرعية 8 و 5 و 2. نقوم بتخزينها بالترتيب الذي تمت زيارتها به. هذا يسمح لنا بزيارة العقد الفرعية للعقدة 8 أولاً (أي 6 و 4 و 3)، ثم العقد الفرعية للعقدة 5 (وهي null)، ثم العقد الفرعية للعقدة 2 (وهي 9) وهكذا.

آلية عمل خوارزمية البحث الأول بالعمق (BFS)

لتطبيق خوارزمية BFS، تُستخدم بنية بيانات الطابور (queue). يقوم الطابور بتخزين العقدة ويضع علامة عليها بأنها 'visited' (تمت زيارتها) حتى يتم وضع علامة على جميع رؤوسها المجاورة. يتبع الطابور مبدأ First In First Out (FIFO)، مما يعني أن جيران العقدة سيتم زيارتهم بالترتيب الذي تم إدخالهم به.

خطوات تطبيق BFS الأساسية:

1. أضف العقدة إلى الطابور (queue).
2. أزل العقدة من الطابور.
3. استرجع الجيران غير المزارين للعقدة التي تمت إزالتها، وأضفهم إلى الطابور.
4. كرر الخطوات 1 و 2 و 3 طالما أن الطابور ليس فارغًا.

الآن دعنا نلقي نظرة على بعض مسائل Leetcode ونطبق ما تعلمناه.

تطبيقات عملية لـ BFS: أمثلة من Leetcode

1. اجتياز شجرة ثنائية بترتيب المستوى (Leetcode 102)

الصعوبة: متوسطة

تطلب منا هذه المسألة اجتياز الرسم البياني وطباعة العقد في كل مستوى في قائمة مرتبطة (linked list). لحل هذه المسألة، كل ما نحتاجه هو تطبيق نمط BFS الأساسي!

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

في التعليمات البرمجية أعلاه، قمنا أولاً بإدخال العقدة الجذرية في الطابور (queue). بينما الطابور ليس فارغًا، قمنا بإزالة هذه العقدة من الطابور وأدخلنا طفليها الأيسر والأيمن في الطابور. ولكن قبل ذلك، تحققنا مما إذا كان كل من طفليها null أم لا. إذا كان null، لكنا حصلنا على استثناء مؤشر فارغ (Null Pointer Exception). تتكرر العملية مرة أخرى مع العناصر التالية التي تبقى في الطابور. يتم الحفاظ على حلقة for لتزويدنا بقائمة العقد في كل مستوى في قوائم مرتبطة منفصلة.

2. متوسط قيم المستويات في شجرة ثنائية (Leetcode 637)

الصعوبة: سهلة

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

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

3. اجتياز شجرة N-ary بترتيب المستوى (Leetcode 429)

الصعوبة: متوسطة

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

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

الخلاصة التقنية

تُعد خوارزمية البحث الأول بالعمق (BFS) أداة لا غنى عنها في عالم هياكل البيانات والخوارزميات، خاصة عند التعامل مع الرسوم البيانية والأشجار. تبرز قوتها في قدرتها على إيجاد أقصر مسار في الرسوم البيانية غير الموزونة (unweighted graphs) وفعاليتها في عمليات الاجتياز بترتيب المستوى. تكمن كفاءتها في استخدام الطابور (queue) لضمان زيارة جميع العقد على مستوى معين قبل الانتقال إلى المستوى التالي، مما يضمن استكشافًا منهجيًا ومنظمًا. فهم نمط BFS الأساسي، كما رأينا في أمثلة Leetcode، يفتح الباب أمام حل مجموعة واسعة من المشكلات المعقدة بكفاءة عالية، مما يجعلها مهارة أساسية لأي مطور أو مهندس برمجيات.

آمل أن يكون هذا الدليل قد ساعدك على فهم BFS بشكل أفضل وأن تكون قد استمتعت به. يرجى التوصية بهذا المنشور إذا كنت تعتقد أنه قد يكون مفيدًا لشخص آخر!