خوارزمية البحث عن العرض الأول (BFS) مع مثال
فريق التحرير
⚡ ملخص ذكي
خوارزمية البحث بالعرض أولاً (BFS) هي خوارزمية تجتاز الرسم البياني مستوىً تلو الآخر، وتزور جميع جيران العقدة قبل الانتقال إلى مستوى أعمق. تستخدم هذه الخوارزمية قائمة انتظار FIFO وتجد أقصر مسار في الرسوم البيانية غير الموزونة دون حلقات لا نهائية.
ما هي خوارزمية BFS (بحث العرض الأول)؟
البحث بالعرض أولاً (BFS) هو خوارزمية تُستخدم لرسم البيانات بيانيًا أو البحث في شجرة أو اجتياز الهياكل. والاسم الكامل لـ BFS هو البحث بالعرض أولاً.
تقوم الخوارزمية بزيارة جميع العقد الرئيسية في الرسم البياني ووضع علامات عليها بشكل دقيق. تحدد هذه الخوارزمية عقدة واحدة (نقطة البداية أو نقطة المصدر) في الرسم البياني ثم تزور جميع العقد المجاورة للعقدة المحددة. تذكر أن BFS تصل إلى هذه العقد واحدة تلو الأخرى.
بمجرد أن تقوم الخوارزمية بزيارة العقدة المبدئية ووضع علامة عليها، فإنها تتحرك نحو أقرب العقد التي لم تتم زيارتها وتحليلها. بمجرد زيارتها، يتم وضع علامة على جميع العقد. تستمر هذه التكرارات حتى تتم زيارة جميع عقد الرسم البياني ووضع علامة عليها بنجاح.
ما هو اجتياز الرسم البياني؟
يعد اجتياز الرسم البياني طريقة شائعة الاستخدام لتحديد موقع قمة الرأس في الرسم البياني. إنها خوارزمية بحث متقدمة يمكنها تحليل الرسم البياني بسرعة ودقة بالإضافة إلى تحديد تسلسل القمم التي تمت زيارتها. تمكنك هذه العملية من زيارة كل عقدة في الرسم البياني بسرعة دون أن تكون مقيدًا في حلقة لا نهائية.
هندسة خوارزمية BFS
- في مختلف مستويات البيانات، يمكنك تحديد أي عقدة كعقدة بداية أو عقدة أولية لبدء عملية التتبع. ستقوم خوارزمية البحث في العرض أولاً (BFS) بزيارة العقدة، ووضع علامة عليها كعقدة تمت زيارتها، ثم إضافتها إلى قائمة الانتظار.
- الآن، ستزور خوارزمية البحث في العرض أولاً أقرب العقد التي لم تتم زيارتها بعد، وستقوم بتحديدها. تُضاف هذه القيم أيضًا إلى قائمة الانتظار. تعمل قائمة الانتظار على نموذج ما يصرف أولاً (FIFO)..
- وبالمثل، يتم تحليل العقد المتبقية الأقرب وغير المزارة على الرسم البياني، ووضع علامات عليها، وإضافتها إلى قائمة الانتظار. تُحذف هذه العناصر من قائمة الانتظار فور استلامها، وتُطبع كنتيجة.
لماذا نحتاج إلى خوارزمية BFS؟
توجد أسباب عديدة لاستخدام خوارزمية البحث في العرض أولاً (BFS) للبحث في مجموعة البيانات الخاصة بك. ومن أهم الجوانب التي تجعل هذه الخوارزمية خيارك الأول ما يلي:
- يعد BFS مفيدًا لتحليل العقد في الرسم البياني وإنشاء أقصر مسار لعبورها.
- يمكن لـ BFS اجتياز الرسم البياني بأقل عدد من التكرارات.
- إن هندسة خوارزمية BFS بسيطة وقوية.
- تتمتع نتيجة خوارزمية BFS بمستوى عالٍ من الدقة مقارنة بالخوارزميات الأخرى.
- تكون تكرارات BFS سلسة، ولا توجد إمكانية لوقوع هذه الخوارزمية في مشكلة حلقة لا نهائية.
كيف تعمل خوارزمية BFS؟
يتطلب اجتياز الرسم البياني أن تقوم الخوارزمية بزيارة و/أو فحص و/أو تحديث كل عقدة لم تتم زيارتها في بنية تشبه الشجرة. يتم تصنيف عمليات اجتياز الرسم البياني حسب الترتيب الذي تزور به العقد على الرسم البياني.
تبدأ خوارزمية البحث المتقدم (BFS) العملية من العقدة الأولى أو العقدة البادئة في الرسم البياني وتجتازها بالكامل. بمجرد اجتياز العقدة الأولية بنجاح، يتم بعد ذلك زيارة الرأس غير المجتاز التالي في الرسم البياني ووضع علامة عليه.
لذا، يمكن القول أنه يتم زيارة جميع العقد المجاورة للرأس الحالي واجتيازها في التكرار الأول. تُستخدم منهجية طابور بسيطة لتنفيذ خوارزمية البحث في العرض أولاً، وتتكون من الخطوات التالية:
الخطوة 1)
كل قمة أو عقدة في الرسم البياني معروفة. على سبيل المثال، يمكنك وضع علامة على العقدة على أنها V.
الخطوة 2)
في حالة عدم الوصول إلى الرأس V، قم بإضافة الرأس V إلى قائمة انتظار BFS.
الخطوة 3)
ابدأ عملية البحث باستخدام خوارزمية البحث في العرض أولاً (BFS)، وبعد الانتهاء، قم بتحديد الرأس V على أنه تمت زيارته.
الخطوة 4)
قائمة انتظار BFS لا تزال غير فارغة، وبالتالي قم بإزالة قمة الرأس V للرسم البياني من قائمة الانتظار.
الخطوة 5)
استرجع جميع الرؤوس المتبقية على الرسم البياني المجاورة للرأس V.
الخطوة 6)
لكل رأس مجاور، لنفترض V1، في حالة عدم زيارته بعد، أضف V1 إلى قائمة انتظار BFS.
الخطوة 7)
سيقوم BFS بزيارة V1، ووضع علامة عليه على أنه تمت زيارته، وحذفه من قائمة الانتظار.
مثال خوارزمية BFS
الخطوة 1)
لديك رسم بياني لسبعة أرقام تتراوح من 0 إلى 6.
الخطوة 2)
تم وضع علامة على 0 أو صفر كعقدة جذر.
الخطوة 3)
تتم زيارة 0 ووضع علامة عليه وإدراجه في بنية بيانات قائمة الانتظار.
الخطوة 4)
يتم زيارة العقد المتبقية المجاورة للصفر والتي لم تتم زيارتها، ووضع علامة عليها، وإدراجها في قائمة الانتظار.
الخطوة 5)
يتم تكرار تكرارات العبور حتى تتم زيارة جميع العقد.
قواعد خوارزمية BFS
فيما يلي قواعد مهمة لاستخدام خوارزمية البحث في العرض أولاً (BFS):
- طابور (FIFO - أول من يدخل أول من يخرج) هيكل البيانات يستخدم من قبل BFS.
- تقوم بتحديد أي عقدة في الرسم البياني كجذر وتبدأ في استعراض البيانات انطلاقاً منها.
- تجتاز خوارزمية البحث في العرض أولاً جميع العقد في الرسم البياني وتستمر في حذفهاping تم الانتهاء منها.
- يقوم BFS بزيارة عقدة مجاورة لم تتم زيارتها، ويضع علامة "تم" عليها، ويدرجها في قائمة الانتظار.
- يقوم هذا الإجراء بإزالة الرأس السابق من قائمة الانتظار في حالة عدم العثور على رأس مجاور.
- تتكرر خوارزمية البحث في العرض أولاً حتى يتم اجتياز جميع الرؤوس في الرسم البياني بنجاح ووضع علامة عليها على أنها مكتملة.
- لا توجد حلقات ناتجة عن BFS أثناء اجتياز البيانات من أي عقدة.
تطبيقات خوارزمية BFS
دعونا نلقي نظرة على بعض التطبيقات الواقعية حيث يمكن أن يكون تنفيذ خوارزمية BFS فعالاً للغاية.
- الرسوم البيانية غير المرجحة: يمكن لخوارزمية البحث في العرض أولاً (BFS) بسهولة إنشاء أقصر مسار وشجرة ممتدة دنيا لزيارة جميع رؤوس الرسم البياني في أقصر وقت ممكن وبدقة عالية.
- شبكات P2P: يمكن تطبيق خوارزمية البحث في العرض أولاً (BFS) لتحديد جميع العقد الأقرب أو المجاورة في شبكة نظير إلى نظير. وهذا من شأنه أن يجد البيانات المطلوبة بشكل أسرع.
- برامج زحف الويب: يمكن لمحركات البحث أو برامج زحف الويب إنشاء مستويات متعددة من الفهارس بسهولة من خلال استخدام BFS. يبدأ تنفيذ BFS من المصدر، وهو صفحة الويب، ثم يقوم بزيارة جميع الروابط من ذلك المصدر.
- أنظمة الملاحة: يمكن لـ BFS المساعدة في العثور على جميع المواقع المجاورة من الموقع الرئيسي أو المصدر.
- البث الشبكي: يتم توجيه الحزمة التي يتم بثها بواسطة خوارزمية BFS للعثور على جميع العقد التي تحتوي على عنوانها والوصول إليها.
