39. البحث بعرض أولاً (Breadth First Search - BFS)

BFS هي خوارزمية اجتياز للرسوم البيانية تستكشف جميع العُقد المجاورة في مستوى العمق الحالي قبل الانتقال إلى العُقد الموجودة في مستوى العمق التالي.

المفهوم: استكشاف الطبقات

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

يستخدم BFS قائمة انتظار (Queue) لتتبع العُقد التي يجب زيارتها بعد ذلك، مما يضمن الاستكشاف مستوى تلو الآخر.

خطوات الخوارزمية

1. البدء من عُقدة المصدر S، وضع علامة عليها كمُزارة، وإضافتها إلى قائمة الانتظار.
2. طالما أن قائمة الانتظار ليست فارغة:
   • إزالة عُقدة U من قائمة الانتظار.
   • لكل جار V لم تتم زيارته لـ U:
     • وضع علامة على V كمُزار، وإضافته إلى قائمة الانتظار.

حالات الاستخدام

• إيجاد أقصر مسار في رسم بياني غير مُوزَّن (لأنه يستكشف أقرب العُقد أولاً).
• زواحف الويب (الزحف مستوى تلو الآخر).