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