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