قبل النظر في الاختلافات بين BFS وDFS، يجب علينا أولاً أن نعرف عن BFS وDFS بشكل منفصل.

ما هو بفس؟

بفس تمثل اتساع البحث الأول . ومن المعروف أيضا باسم اجتياز ترتيب المستوى . يتم استخدام بنية بيانات قائمة الانتظار لاجتياز Broadth First Search. عندما نستخدم خوارزمية BFS للاجتياز في الرسم البياني، يمكننا اعتبار أي عقدة بمثابة عقدة جذر.

دعونا نفكر في الرسم البياني أدناه لعرض اجتياز البحث الأول.

المهمة المستحيلة جميع الأفلام

لنفترض أننا نعتبر العقدة 0 بمثابة عقدة جذر. لذلك، سيبدأ العبور من العقدة 0.

بمجرد إزالة العقدة 0 من قائمة الانتظار، تتم طباعتها ووضع علامة عليها كـ a العقدة التي تمت زيارتها.

بمجرد إزالة العقدة 0 من قائمة الانتظار، سيتم إدراج العقد المجاورة للعقدة 0 في قائمة الانتظار كما هو موضح أدناه:

الآن ستتم إزالة العقدة 1 من قائمة الانتظار؛ تتم طباعتها ووضع علامة عليها كعقدة تمت زيارتها

بمجرد إزالة العقدة 1 من قائمة الانتظار، ستتم إضافة جميع العقد المجاورة للعقدة 1 إلى قائمة الانتظار. العقد المجاورة للعقدة 1 هي 0، 3، 2، 6، و5. لكن يتعين علينا إدراج العقد غير التي تمت زيارتها فقط في قائمة الانتظار. نظرًا لأن العقد 3 و2 و6 و5 لم تتم زيارتها؛ لذلك، سيتم إضافة هذه العقد في قائمة الانتظار كما هو موضح أدناه:

العقدة التالية هي 3 في قائمة الانتظار. لذلك، ستتم إزالة العقدة 3 من قائمة الانتظار، وستتم طباعتها ووضع علامة عليها كمزار كما هو موضح أدناه:

بمجرد إزالة العقدة 3 من قائمة الانتظار، ستتم إضافة جميع العقد المجاورة للعقدة 3 باستثناء العقد التي تمت زيارتها في قائمة الانتظار. العقد المجاورة للعقدة 3 هي 0 و1 و2 و4. وبما أن العقد 0 و1 تمت زيارتها بالفعل، والعقدة 2 موجودة في قائمة الانتظار؛ ولذلك، نحن بحاجة إلى إدراج العقدة 4 فقط في قائمة الانتظار.

منحدر غير محدد

الآن، العقدة التالية في قائمة الانتظار هي 2. لذا، سيتم حذف 2 من قائمة الانتظار. تتم طباعته ووضع علامة عليه كما هو موضح أدناه:

بمجرد إزالة العقدة 2 من قائمة الانتظار، ستتم إضافة جميع العقد المجاورة للعقدة 2 باستثناء العقد التي تمت زيارتها في قائمة الانتظار. العقد المجاورة للعقدة 2 هي 1 و3 و5 و6 و4. وبما أن العقد 1 و3 تمت زيارتها بالفعل، وتمت إضافة 4 و5 و6 بالفعل إلى قائمة الانتظار؛ لذلك، لا نحتاج إلى إدراج أي عقدة في قائمة الانتظار.

العنصر التالي هو 5. لذا، سيتم حذف 5 من قائمة الانتظار. تتم طباعته ووضع علامة عليه كما هو موضح أدناه:

بمجرد إزالة العقدة 5 من قائمة الانتظار، ستتم إضافة جميع العقد المجاورة للعقدة 5 باستثناء العقد التي تمت زيارتها في قائمة الانتظار. العقد المجاورة للعقدة 5 هي 1 و 2. وبما أن كلا العقدتين قد تمت زيارتهما بالفعل؛ لذلك، لا يوجد أي قمة لإدراجها في قائمة الانتظار.

العقدة التالية هي 6. لذا، سيتم حذف 6 من قائمة الانتظار. تتم طباعته ووضع علامة عليه كما هو موضح أدناه:

بمجرد إزالة العقدة 6 من قائمة الانتظار، ستتم إضافة جميع العقد المجاورة للعقدة 6 باستثناء العقد التي تمت زيارتها في قائمة الانتظار. العقد المجاورة للعقدة 6 هي 1 و4. وبما أن العقدة 1 قد تمت زيارتها بالفعل وتمت إضافة العقدة 4 بالفعل إلى قائمة الانتظار؛ لذلك، لا توجد قمة ليتم إدراجها في قائمة الانتظار.

العنصر التالي في قائمة الانتظار هو 4. لذا، سيتم حذف 4 من قائمة الانتظار. تتم طباعته ووضع علامة عليه كزيارة.

التعليقات التوضيحية في التمهيد الربيع

بمجرد إزالة العقدة 4 من قائمة الانتظار، ستتم إضافة جميع العقد المجاورة للعقدة 4 باستثناء العقد التي تمت زيارتها في قائمة الانتظار. العقد المجاورة للعقدة 4 هي 3 و2 و6. وبما أن جميع العقد المجاورة قد تمت زيارتها بالفعل؛ لذلك، لا توجد قمة يمكن إدراجها في قائمة الانتظار.

ما هو DFS؟

DFS لتقف على عمق البحث الأول. في اجتياز DFS، يتم استخدام بنية بيانات المكدس، والتي تعمل على مبدأ LIFO (آخر ما يدخل أولاً يخرج). في DFS، يمكن بدء العبور من أي عقدة، أو يمكننا القول أنه يمكن اعتبار أي عقدة بمثابة عقدة جذر حتى لا يتم ذكر العقدة الجذرية في المشكلة.

في حالة BFS، العنصر الذي تم حذفه من قائمة الانتظار، تتم إضافة العقد المجاورة للعقدة المحذوفة إلى قائمة الانتظار. في المقابل، في DFS، العنصر الذي تتم إزالته من المكدس، تتم إضافة عقدة واحدة مجاورة فقط للعقدة المحذوفة في المكدس.

دعونا ننظر في الرسم البياني أدناه لاجتياز العمق الأول للبحث.

اعتبر العقدة 0 بمثابة عقدة جذر.

أولا نقوم بإدخال العنصر 0 في المكدس كما هو موضح أدناه:

تحتوي العقدة 0 على عقدتين متجاورتين، أي 1 و3. الآن يمكننا أن نأخذ عقدة واحدة متجاورة فقط، إما 1 أو 3، للعبور. لنفترض أننا نعتبر العقدة 1؛ لذلك، يتم إدراج 1 في المكدس ويتم طباعته كما هو موضح أدناه:

الآن سوف ننظر إلى القمم المجاورة للعقدة 1. القمم المجاورة غير المزارة للعقدة 1 هي 3 و 2 و 5 و 6. يمكننا النظر في أي من هذه القمم الأربعة. لنفترض أننا أخذنا العقدة 3 وأدخلناها في المكدس كما هو موضح أدناه:

خذ بعين الاعتبار القمم المجاورة غير المزارة للعقدة 3. القمم المجاورة غير المزارة للعقدة 3 هي 2 و 4. يمكننا أن نأخذ أيًا من الرؤوس، أي 2 أو 4. لنفترض أننا أخذنا الرأس 2 وأدخلناه في المكدس كما هو موضح أدناه:

القمم المجاورة غير المزارة للعقدة 2 هي 5 و4. يمكننا اختيار أي من القمم، أي 5 أو 4. لنفترض أننا أخذنا الرأس 4 وأدخلناه في المكدس كما هو موضح أدناه:

الآن سننظر في القمم المجاورة غير المزارة للعقدة 4. القمم المجاورة غير المزارة للعقدة 4 هي العقدة 6. لذلك، يتم إدراج العنصر 6 في المكدس كما هو موضح أدناه:

محاذاة صورة المغلق

بعد إدراج العنصر 6 في المكدس، سننظر إلى القمم المجاورة غير المزارة للعقدة 6. نظرًا لعدم وجود رؤوس مجاورة غير تمت زيارتها للعقدة 6، لذلك لا يمكننا تجاوز العقدة 6. في هذه الحالة، سنقوم بإجراء التراجع . سيتم إخراج العنصر العلوي، أي 6، من المكدس كما هو موضح أدناه:

البديل xampp

العنصر العلوي في المكدس هو 4. نظرًا لعدم وجود رؤوس مجاورة غير مرغوب فيها على اليسار من العقدة 4؛ لذلك، يتم إخراج العقدة 4 من المكدس كما هو موضح أدناه:

العنصر العلوي التالي في المكدس هو 2. الآن، سننظر إلى القمم المجاورة غير المزارة للعقدة 2. نظرًا لأنه لم يتبق سوى عقدة واحدة غير مزارة، أي 5، لذلك سيتم دفع العقدة 5 إلى المكدس فوق 2 وتتم طباعتها كما هو مبين أدناه:

الآن سوف نتحقق من القمم المجاورة للعقدة 5، والتي لم تتم زيارتها بعد. نظرًا لعدم وجود قمة متبقية لزيارتها، فإننا نخرج العنصر 5 من المكدس كما هو موضح أدناه:

لا يمكننا التحرك أكثر من 5، لذلك نحن بحاجة إلى إجراء التراجع. في التراجع، سيتم إخراج العنصر العلوي من المكدس. العنصر العلوي هو 5 الذي سيتم إخراجه من المكدس، ونعود إلى العقدة 2 كما هو موضح أدناه:

الآن سوف نتحقق من القمم المجاورة غير المزارة للعقدة 2. نظرًا لعدم وجود قمة مجاورة متبقية لزيارتها، لذلك نقوم بإجراء التراجع. في التراجع، سيتم إخراج العنصر العلوي، أي 2، من المكدس، ونعود إلى العقدة 3 كما هو موضح أدناه:

الآن سوف نتحقق من القمم المجاورة غير المزارة للعقدة 3. نظرًا لعدم وجود قمة مجاورة متبقية لزيارتها، لذلك نقوم بإجراء التراجع. في التراجع، سيتم إخراج العنصر العلوي، أي 3، من المكدس ونعود إلى العقدة 1 كما هو موضح أدناه:

بعد ظهور العنصر 3، سوف نتحقق من القمم المجاورة غير المزارة للعقدة 1. نظرًا لعدم وجود قمة متبقية لزيارتها؛ ولذلك، سيتم تنفيذ التراجع. في التراجع، سيتم إخراج العنصر العلوي، أي 1، من المكدس، ونعود إلى العقدة 0 كما هو موضح أدناه:

سوف نتحقق من القمم المجاورة للعقدة 0، والتي لم تتم زيارتها بعد. نظرًا لعدم وجود قمة مجاورة متبقية لزيارتها، لذلك نقوم بإجراء عملية التراجع. في هذا، سيتم إخراج عنصر واحد فقط، أي 0 في المكدس، من المكدس كما هو موضح أدناه:

كما نلاحظ في الشكل أعلاه أن المكدس فارغ. لذلك، علينا إيقاف اجتياز DFS هنا، والعناصر التي تتم طباعتها هي نتيجة اجتياز DFS.

الاختلافات بين BFS وDFS

فيما يلي الاختلافات بين BFS وDFS: