البحث بالعرض أولًا (BFS)
يستكشف المخطط طبقة بعد طبقة. الطابور يحدد الرأس التالي، لذلك تُزار الرؤوس الأقرب دائمًا أولًا.
- الوقت O(V + E)
- الذاكرة O(V)
- يستخدم طابورًا
ماذا تعني هذه المصطلحات؟
- الرأس: نقطة في المخطط، مرسومة هنا كدائرة فيها حرف.
- الحافة: خط يصل بين رأسين. يمكنك هنا السير عليه في الاتجاهين.
- الجيران: الرؤوس المتصلة برأس ما عبر حافة. تُفحص بالترتيب الأبجدي.
- الطابور: الداخل أولًا يخرج أولًا. يأخذ BFS دائمًا الرأس الذي انتظر أطول مدة.
- المكدس: الداخل أخيرًا يخرج أولًا. يتابع DFS دائمًا من آخر رأس وصل إليه.
- V و E: عدد الرؤوس وعدد الحواف. تعني O(V + E) أن كل رأس وكل حافة يُعالَجان عددًا ثابتًا من المرات.
- في الطابور
- الحالي
- انتهى
- حافة في شجرة البحث
- حافة متخطّاة
ابدأ من A. اضغط تشغيل أو تقدّم في البحث خطوة بخطوة.
مفتاح المسافة: تشغيل أو إيقاف مؤقت. السهمان الأيسر والأيمن: خطوة بخطوة. Home وEnd: الانتقال المباشر.
جرّب هذا: اختر المخطط ذا الجزأين. الرؤوس غير المتصلة برأس البداية لا يُوصَل إليها أبدًا.
كيف يعمل
يضع BFS رأس البداية في طابور. ثم يكرر الأمر نفسه مرة بعد مرة: يأخذ الرأس الذي في مقدمة الطابور ويضيف جيرانه الجدد إلى آخره. يخدم الطابور حسب ترتيب الوصول، لذا ينتهي كل رأس يبعد حافة واحدة قبل أي رأس يبعد حافتين. الرقم بجانب الرأس هو مسافته عن البداية: أقل عدد من الحواف يلزم للوصول إليه.
متى يكون خيارًا جيدًا
استخدم BFS عندما تحتاج أقصر طريق بعدد الخطوات: أقل عدد من الحركات في لغز، أو أقل عدد من القفزات في شبكة، أو الأشخاص الذين يبعدون عنك معرفتين على الأكثر. في المخطط الكبير قد يطول الطابور، لأنه يحمل طبقة كاملة دفعة واحدة.