- الحالية
- في الطابور
- تمت زيارتها
- المسار
البحث بالعرض أولاً (BFS)
يستكشف البحث بالعرض أولاً الرسم البياني على شكل حلقات: أولاً كل عقدة مجاورة للبداية، ثم كل عقدة تبعد حافتين، وهكذا. ويفعل ذلك بطابور، ما يدخل أولاً يخرج أولاً. انقر على عقدة لتبدأ منها، واختر هدفًا إن شئت، ثم تقدّم في البحث خطوة بخطوة لترى الطابور يطول ويقصر، وكل عقدة تأخذ مسافتها، وأقصر مسار يظهر. اضغط «تشغيل» لمشاهدة البحث، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. انقر على عقدة لتجعلها البداية؛ وحوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى للبحث عن أقصر مسار إليها. الرقم على كل عقدة هو مسافتها من البداية، والصف أسفل الرسم البياني هو الطابور. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- انقر على عقدة لتجعلها البداية. للبحث عن مسار، حوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى.
- اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
- راقب الطابور أسفل الرسم البياني والمسافة على كل عقدة. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.
كيف يعمل البحث بالعرض أولاً
ضع عقدة البداية في الطابور بمسافة 0. ثم كرّر: خذ العقدة التي في مقدمة الطابور وانظر إلى كل جار من جيرانها. الجار الذي لم يُرَ بعد يحصل على مسافة أكبر بواحد من العقدة المأخوذة، ويتذكر تلك العقدة على أنها الطريق الذي بُلغ منه، وينضم إلى آخر الطابور. ويُتخطى الجيران الذين رُئوا من قبل. وعندما يفرغ الطابور، تكون لكل عقدة يمكن بلوغها مسافتها.
لماذا يجد أقصر المسارات
يُخرج الطابور العقد بالترتيب الذي وُجدت به، وتُوجد العقد حلقة بعد حلقة: كل العقد على المسافة 1 تدخل الطابور قبل أي عقدة على المسافة 2، وهكذا. لذلك عندما تُبلغ عقدة لأول مرة، تُبلغ بمسار فيه أقل عدد ممكن من الحواف. وتتبُّع العقد المحفوظة من الهدف رجوعًا إلى البداية يعطي هذا المسار. وهذا يعدّ الحواف فقط؛ فإذا اختلفت أطوال الحواف، احتجنا إلى خوارزمية ديكسترا.
الأسئلة المتداولة
ما البحث بالعرض أولاً؟
طريقة لاستكشاف رسم بياني من عقدة بداية بزيارة كل جيرانها أولاً، ثم جيرانهم، وهكذا، حلقة بعد حلقة. ويستخدم طابورًا ليُبقي العقد بالترتيب الذي وُجدت به.
هل يجد البحث بالعرض أولاً أقصر مسار؟
نعم، عندما تُحسب كل الحواف بالقدر نفسه: أول مرة يبلغ فيها BFS عقدة ما، يكون قد استخدم أقل عدد ممكن من الحواف. أما إذا اختلفت أطوال الحواف، فاستخدم خوارزمية ديكسترا بدلاً منه.
ما الفرق بين BFS وDFS؟
البحث بالعرض أولاً يستخدم طابورًا وينتشر بالتساوي، حلقة بعد حلقة. والبحث بالعمق أولاً يستخدم مكدسًا (أو العودية) ويتبع مسارًا واحدًا إلى أبعد عمق ممكن قبل أن يتراجع. يجد BFS أقصر المسارات بعدد الحواف؛ أما DFS فلا، لكنه مفيد لإيجاد الدورات وللترتيب الطوبولوجي.
ما سرعة البحث بالعرض أولاً؟
يُخرج كل عقدة من الطابور مرة واحدة وينظر إلى كل حافة من طرفيها، فيزداد العمل مع عدد العقد مضافًا إليه عدد الحواف.
هل يُرسل الرسم البياني إلى أي مكان؟
لا. يُنشأ الرسم البياني ويُبحث فيه داخل متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر