BFS مقابل DFS – الفرق بينهما
سارة تشين
الفرق الرئيسي بين BFS و DFS
- يبحث BFS عن أقصر مسار إلى الوجهة، بينما يذهب DFS إلى أسفل الشجرة الفرعية، ثم يتراجع.
- الشكل الكامل لـ BFS هو بحث العمق الأول، في حين أن الشكل الكامل لـ DFS هو بحث العمق الأول.
- يستخدم BFS قائمة انتظار لتتبع الموقع التالي للزيارة. بينما يستخدم DFS مكدسًا لتتبع الموقع التالي الذي سيتم زيارته.
- يجتاز BFS وفقًا لمستوى الشجرة، بينما يجتاز DFS وفقًا لعمق الشجرة.
- يتم تنفيذ BFS باستخدام قائمة FIFO؛ ومن ناحية أخرى، يتم تنفيذ DFS باستخدام قائمة LIFO.
- في BFS، لا يمكن أبدًا أن تكون محاصرًا في حلقات محدودة، بينما في DFS، يمكن أن تكون محاصرًا في حلقات لا نهائية.
ما هو BFS؟
BFS هي خوارزمية تُستخدم لرسم البيانات بيانيًا أو البحث في الشجرة أو عبور الهياكل. تقوم الخوارزمية بزيارة ووضع علامات على جميع العقد الرئيسية في الرسم البياني بشكل دقيق.
تختار هذه الخوارزمية عقدة واحدة (نقطة البداية أو نقطة المصدر) في الرسم البياني ثم تزور جميع العقد المجاورة للعقدة المحددة. وبمجرد أن تزور الخوارزمية العقدة المبدئية وتضع علامة عليها، تنتقل بعد ذلك إلى أقرب العقد غير المزارة وتحللها.
بمجرد زيارتها، يتم وضع علامة على جميع العقد. تستمر هذه التكرارات حتى تتم زيارة جميع عقد الرسم البياني ووضع علامة عليها بنجاح. الشكل الكامل لـ BFS هو بحث العرض الأول.
ما هو DFS؟
DFS عبارة عن خوارزمية للعثور على الرسوم البيانية أو الأشجار أو اجتيازها في اتجاه العمق. يبدأ تنفيذ الخوارزمية عند العقدة الجذرية ويستكشف كل فرع قبل التراجع. يستخدم بنية بيانات مكدسة للتذكر، والحصول على القمة اللاحقة، وبدء البحث، عندما يظهر طريق مسدود في أي تكرار. الشكل الكامل لـ DFS هو بحث العمق الأول.
الفرق بين BFS وشجرة DFS الثنائية
فيما يلي الاختلافات المهمة بين BFS و DFS.
| BFS | DFS |
|---|---|
| BFS يجد أقصر طريق إلى الوجهة. | ينتقل DFS إلى أسفل الشجرة الفرعية، ثم يتراجع. |
| الشكل الكامل لـ BFS هو بحث العرض الأول. | الشكل الكامل لـ DFS هو Depth First Search. |
| ويستخدم قائمة انتظار لتتبع الموقع التالي للزيارة. | ويستخدم مكدس لتتبع الموقع التالي للزيارة. |
| يجتاز BFS وفقًا لمستوى الشجرة. | يجتاز DFS وفقًا لعمق الشجرة. |
| يتم تنفيذه باستخدام قائمة FIFO. | يتم تنفيذه باستخدام قائمة LIFO. |
| يتطلب المزيد من الذاكرة مقارنة بـ DFS. | يتطلب ذاكرة أقل مقارنة بـ BFS. |
| تعطي هذه الخوارزمية حل المسار الضحل. | لا تضمن هذه الخوارزمية الوصول إلى حل المسار الضحل. |
| ليست هناك حاجة للتراجع في BFS. | هناك حاجة للتراجع في DFS. |
| لا يمكنك أبدًا أن تكون محاصرًا في حلقات محدودة. | يمكن أن تكون محاصرا في حلقات لا نهاية لها. |
| إذا لم تجد أي هدف، فقد تحتاج إلى توسيع العديد من العقد قبل العثور على الحل. | إذا لم تجد أي هدف، فقد يحدث تراجع في العقدة الورقية. |
مثال على BFS
في المثال التالي لـ BFS، استخدمنا رسمًا بيانيًا يحتوي على 6 رؤوس.
مثال على BFS
الخطوة 1)
لديك رسم بياني مكون من سبعة أرقام تتراوح من 0 إلى 6.
الخطوة 2)
تم وضع علامة على 0 أو صفر كعقدة جذر.
الخطوة 3)
تتم زيارة 0 ووضع علامة عليه وإدراجه في بنية بيانات قائمة الانتظار.
الخطوة 4)
تتم زيارة العقد المجاورة وغير التي لم تتم زيارتها المتبقية ووضع علامة عليها وإدراجها في قائمة الانتظار.
الخطوة 5)
يتم تكرار تكرارات العبور حتى تتم زيارة جميع العقد.
مثال على DFS
في المثال التالي لـ DFS، استخدمنا رسمًا بيانيًا غير موجه يحتوي على 5 رؤوس.
الخطوة 1)
لقد بدأنا من الرأس 0. تبدأ الخوارزمية بوضعه في القائمة التي تمت زيارتها ووضع جميع الرؤوس المجاورة له في نفس الوقت في القائمة التي تمت زيارتها. هيكل البيانات يسمى المكدس.
الخطوة 2)
ستزور العنصر الموجود أعلى المكدس، على سبيل المثال، 1 وتنتقل إلى العقد المجاورة له. هذا لأنه تمت زيارة 0 بالفعل. ولذلك، فإننا نزور قمة 2.
الخطوة 3)
لدى Vertex 2 قمة قريبة غير مرغوب فيها في 4. لذلك، نضيفها إلى المكدس ونقوم بزيارتها.
الخطوة 4)
أخيرًا، سنزور القمة الثالثة الأخيرة، حيث لا تحتوي على أي عقد مجاورة لم تتم زيارتها. لقد أكملنا اجتياز الرسم البياني باستخدام خوارزمية DFS.
تطبيقات BFS
فيما يلي تطبيقات BFS:
الرسوم البيانية غير المرجحة
يمكن لخوارزمية BFS بسهولة إنشاء أقصر مسار والحد الأدنى من الشجرة الممتدة لزيارة جميع رؤوس الرسم البياني في أقصر وقت ممكن وبدقة عالية.
شبكات P2P
يمكن تنفيذ BFS لتحديد موقع جميع العقد الأقرب أو المجاورة في شبكة نظير إلى نظير. سيؤدي هذا إلى العثور على البيانات المطلوبة بشكل أسرع.
برامج زحف الويب
محركات البحث أو يمكن لبرامج زحف الويب إنشاء مستويات متعددة من الفهارس بسهولة من خلال استخدام BFS. يبدأ تنفيذ BFS من المصدر، وهو صفحة الويب، ثم يقوم بزيارة جميع الروابط من ذلك المصدر.
البث الشبكي
يتم توجيه الحزمة التي يتم بثها بواسطة خوارزمية BFS للعثور على جميع العقد التي تحتوي على عنوانها والوصول إليها.
تطبيقات DFS
فيما يلي تطبيقات مهمة لـ DFS:
الرسم البياني المرجح
في الرسم البياني الموزون، يؤدي اجتياز الرسم البياني DFS إلى إنشاء أقصر شجرة مسار والحد الأدنى من الشجرة الممتدة.
الكشف عن دورة في الرسم البياني
يحتوي الرسم البياني على دورة إذا وجدنا حافة خلفية أثناء DFS. لذلك، يجب علينا تشغيل DFS للرسم البياني والتحقق من الحواف الخلفية.
العثور على المسار
يمكننا أن نتخصص في خوارزمية DFS للبحث عن مسار بين قمتين.
الفرز الطوبولوجي
تُستخدم في المقام الأول لجدولة المهام من التبعيات المعطاة ضمن مجموعة المهام. وفي علوم الكمبيوتر، تُستخدم في جدولة التعليمات، وتسلسل البيانات، والتوليف المنطقي، وتحديد ترتيب مهام التجميع.
البحث عن مكونات الرسم البياني المترابطة بقوة
يتم استخدامه في الرسم البياني DFS عندما يكون هناك مسار من كل قمة في الرسم البياني إلى القمم الأخرى المتبقية.
حل الألغاز بحل واحد فقط
يمكن تكييف خوارزمية DFS بسهولة للبحث في جميع الحلول للمتاهة من خلال تضمين العقد الموجودة على المسار الحالي في المجموعة التي تمت زيارتها.
