خوارزمية بحث العرض أولا BFS

ما هي خوارزمية البحث بالعرض أولا BFS؟

البحث بالعرض أولاً (Breadth-first search)، هي عبارة عن خوارزمية تَستخدم بيانات الرسم البياني (graph) أو شجرة البحث (trees)، حيث تُحدد هذه الخوارزمية عقدة واحدة (نقطة أولية) في رسم البياني ثم تزور جميع العقد المرتبطة بهذه العقدة، وتقوم بوضع علامة على كل عقدة تزورها (لكي لا يتم زيارتها مرة أخرى)، تستمر هذه العملية حتى يتم زيارة جميع عُقد الرسم البياني وتمييزها. تذكر أن (BFS) تصل إلى هذه العقد واحدة تلو الأخرى دون تكرار.

مثال على آلية عمل خوارزمية BFS:

سنستخدم في هذا المثال ما يلي:

• رسم بياني غير موجه (undirect graph) مكون من سبع عقد (nodes) تم ترقيمهم (من 1 إلى 6).

• مصفوفة (array) من نوع (Boolean)، مع إضافة قيم ابتدائية للمصفوفة كاملة (= 0) تشير الى أن أي من العقد  لم يتم زيارتهم بعد، وهذه المصفوفة لتجنب زيارة العقدة (node) أكثر من مرة.

• (queue) من نوع (int)، لإضافة جميع العقد المجاورة للعقدة الحالية فيها.

الخطوة الأولى:

• ابدأ بوضع العقدة رقم (1) في الـ (queue)، خذ العنصر الأمامي من الـ (queue)، وبمكان (0) في المصفوفة نضع (1) أي أنه قد تم زيارته.

الخطوة الثانية:

• بعد إزالة (1) من ال (queue)، نقوم بإدراج العقد المجاورة ل (1) التي لم تتم زيارتها ل (queue)، وتعليم مكانهم في المصفوفة أنه تم زيارتهم.

• في كل مرة نخرج من ال (queue) إحدى العقد، فأننا نعلمه بانه تم زيارته؛ بأن نضع مكانه في المصفوفة قيمة (1)، و ندرج العقد المجاورة له في ال (queue)، نكرر هذه العملية حتى تصبح ال (queue) فارغة.

كود الخوارزمية باستخدام لغة ++C:

ما هو تعقيد الوقت Time Complexity في خوارزمية BFS؟

تعقيد الوقت هو (O(V+E، حيث أن (V) هو عدد العقد (nodes)، و(E) هو عدد الحواف (edges) في الرسم البياني (graph).

تطبيقات خوارزمية BFS:

التطبيقات الواقعية حيث يمكن أن يكون تنفيذ خوارزمية BFS فعالاً للغاية في:

• الرسوم البيانية غير الموزونة: يمكن لخوارزمية (BFS) بسهولة إنشاء أقصر مسار لزيارة جميع (nodes) الرسم البياني في أقصر وقت ممكن وبدقة عالية.

• شبكات (P2P): يمكن تنفيذ (BFS) لتحديد موقع جميع (nodes) الأقرب أو المجاورة في شبكة نظير الى نظير (peer to peer)، سيجد هذا البيانات المطلوبة بشكل أسرع.

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

• أنظمة الملاحة: يمكن أن تساعد (BFS) في العثور على جميع المواقع المجاورة، من الموقع الرئيسي (موقعك مثلاً).

• بث الشبكة: تُوجيه الحزمة التي يتم بثها بواسطة خوارزمية (BFS) للعثور والوصول على جميع العقد التي لديها نفس العنوان.