تمت زيارتها
في المكدس
الحواف المفحوصة

  • الحالية
  • في المكدس
  • منتهية
  • المسار
النقر على عقدة يحدد

مزيد عن البحث بالعمق أولاً

البحث بالعمق أولاً (DFS)

يستكشف البحث بالعمق أولاً الرسم البياني كمن يسير في متاهة ويده على الجدار: يتبع مسارًا واحدًا إلى أبعد ما يصل، ولا يتراجع إلا حين لا يبقى مكان جديد يذهب إليه. ويفعل ذلك بمكدس. انقر على عقدة لتبدأ منها، واختر هدفًا إن شئت، وتقدّم في البحث خطوة بخطوة لترى المكدس يكبر ويصغر، وكل عقدة تنال رقم زيارتها، والحواف التي تُغلق دورة. اضغط «تشغيل» لمشاهدة البحث، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. انقر على عقدة لتجعلها البداية؛ وحوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى للبحث عن مسار إليها. الرقم على كل عقدة هو ترتيب زيارتها، والصف أسفل الرسم البياني هو المكدس، من البداية حتى العقدة التي في القمة. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. انقر على عقدة لتجعلها البداية. للبحث عن مسار، حوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى.
  2. اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
  3. راقب المكدس أسفل الرسم البياني ورقم الزيارة على كل عقدة. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.

كيف يعمل البحث بالعمق أولاً

ضع عقدة البداية في المكدس. ثم كرّر: انظر إلى الجار التالي للعقدة التي في قمة المكدس. الجار الذي لم يُرَ بعد يحصل على رقم الزيارة التالي، ويتذكر العقدة التي بُلغ منها، ويوضع في قمة المكدس، فيواصل البحث من هناك. وحين لا يبقى للعقدة التي في القمة جيران لفحصها، تنتهي وتُرفع من المكدس، ويتراجع البحث إلى العقدة التي تحتها. وحين يصبح المكدس فارغًا، تكون كل عقدة يمكن بلوغها قد تمت زيارتها.

ما يخبرك به المكدس

لأن البحث يواصل دائمًا من أحدث عقدة، يكون المكدس دائمًا مسارًا من البداية إلى العقدة قيد الفحص. وحين يُبلغ الهدف، يكون المكدس مسارًا إليه، وإن لم يكن في الغالب الأقصر: فذلك ما يجده البحث بالعرض أولاً. في رسم بياني غير موجّه، الحافة إلى عقدة ما زالت في المكدس، غير التي جاء منها للتو، تُغلق دورة. والعقد التي يتذكرها البحث تشكّل شجرة، هي شجرة البحث بالعمق أولاً، وترتيب انتهاء العقد هو مفتاح الترتيب الطوبولوجي.

الأسئلة المتداولة

ما البحث بالعمق أولاً؟

طريقة لاستكشاف رسم بياني من عقدة بداية باتباع مسار واحد إلى أعمق ما يصل، والتراجع لتجربة فرع آخر فقط حين لا يبقى مكان جديد يذهب إليه. يستخدم مكدسًا، أو العودية، ليتذكر طريق العودة.

هل يجد البحث بالعمق أولاً أقصر مسار؟

لا. يجد مسارًا إلى الهدف إن وُجد، لكن هذا المسار قد يكون أطول بكثير من اللازم، لأن DFS يلتزم بأول فرع يجرّبه. استخدم البحث بالعرض أولاً لأقل عدد من الحواف، أو خوارزمية دايكسترا حين يكون للحواف أطوال.

ما الفرق بين DFS وBFS؟

يستخدم البحث بالعمق أولاً مكدسًا ويتعمق في مسار واحد قبل أن يتراجع. ويستخدم البحث بالعرض أولاً طابورًا وينتشر بالتساوي، حلقة بعد حلقة. كلاهما يزور كل عقدة يمكن بلوغها في وقت يزداد مع عدد العقد زائد عدد الحواف؛ يجد BFS أقصر المسارات، بينما DFS هو الخيار الطبيعي للدورات والمتاهات والترتيب الطوبولوجي.

كيف يجد DFS دورة؟

في رسم بياني غير موجّه، إذا صادف البحث حافة إلى عقدة ما زالت في المكدس، ولم تكن تلك العقدة هي التي جاء منها للتو، فإن الحافة تُغلق حلقة. في التطبيق، يذكر سطر الحالة ذلك حين يحدث.

هل يُرسل الرسم البياني إلى أي مكان؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر