BFS و DFS كلاهما حيوي لنتائج الرسم البياني. يرمز BFS إلى بحث Breadth-First Search ، و DFS لتقف على Depth-First Search. كلاهما يميز بين اثنين. كلاهما يستخدم بنية بيانات مختلفة للأداء ، أحدهما يستخدم بنية بيانات قائمة الانتظار ، والآخر هو بنية البيانات المكدسة.
BFS مقابل DFS
يتمثل الاختلاف الرئيسي بين BFS و DFS في أن Breadth-First Search عبارة عن تقنية تعتمد على الرأس تساعد في الإشارة إلى أقصر مسار في الرسم البياني. من ناحية أخرى ، فإن DFS أو Depth First Search هي تقنية تعتمد على الحافة. BFS هي تقنية تعتمد على بنية بيانات قائمة الانتظار. من ناحية أخرى ، يعتمد DFS على بنية بيانات المكدس.
BFS هي تقنية يتم تطبيقها لمعرفة أقصر مسار في الرسم البياني باستخدام بنية بيانات قائمة الانتظار. إنه مناسب لإيجاد الرؤوس داخل مناطق قريبة من المصدر. على عكس DFS ، لا يمكن تطبيقه بشكل أفضل في أشجار صنع القرار الموجودة في الألغاز أو الألعاب.
DFS هي تقنية يتم تطبيقها لاكتشاف أقصر مسار في الرسم البياني باستخدام بنية البيانات المكدسة. إنه مناسب للمناطق البعيدة عن المصادر داخل الحل. على عكس BFS ، يمكن تطبيقه بشكل أفضل في صنع القرار أو حل المشكلات في الألعاب.
جدول المقارنة بين BFS و DFS
| معلمات المقارنة | BFS | DFS |
| الشكل الكامل والتعريف | BFS لتقف على اتساع البحث الأول. إنها تقنية تعتمد على الرأس وتُستخدم للعثور على أقصر طريق في الرسم البياني. | DFS هي اختصار لـ Depth First Search. إنها تقنية تعتمد على الحواف للعثور على أقصر طريق في الرسم البياني. |
| الاعتماد على بنية البيانات | يحدد Breadth-First Search أو BFS أقصر مسار في الرسم البياني بمساعدة بنية بيانات قائمة الانتظار. | يحدد Depth First Search أو DFS أقصر مسار في الرسم البياني بمساعدة بنية بيانات Stack. |
| الاستخدامات | في الرسم البياني غير الموزون ، يتم استخدامه للعثور على أقصر مسار لمصدر واحد لأنه يستخدم أقل عدد من الحواف من مصدر الرأس. | في DFS ، للوصول إلى نقطة وجهة أو قمة من أي مصدر ، يجب اجتياز المزيد من الحواف. |
| مجال الملاءمة | مجال ملاءمتها لإيجاد نطاقات الرؤوس ضمن مدى قريب من المصدر. إنها غير مناسبة لصنع أشجار القرار الموجودة في الألعاب. | مجال ملاءمتها تتراوح ضمن حلول بعيدة عن المصدر. إنه أكثر ملاءمة لصنع القرار أو المشاكل في الألعاب أو الألغاز. |
| آلية | في هذه التقنية ، يتم اختيار رأس واحد في كل مرة أثناء زيارته ويتم تمييزه بعد ذلك يتم زيارة المنطقة المجاورة وتخزينها في قائمة الانتظار. | يتم وضع القمم التي تمت زيارتها في المكدس ثم في حالة عدم وجود الرؤوس ، يتم تفرقع القمم التي تمت زيارتها. |
ما هو BFS؟
بمساعدة BFS ، يتم اجتياز الرسم البياني في الخبز باتجاه الحركة. لتذكر إحضار الرأس التالي ، يتم استخدام قائمة انتظار في هذه التقنية. يحدث هذا عندما يواجه طريق مسدود في التكرار. لا يتم اعتباره لأشجار القرار لأنه يضم جميع الجيران إلى حد كبير. إنه بطيء نسبيًا من DFS. التعقيد الزمني لخوارزمية BFS هو O (V + E) أثناء وقت القائمة المجاورة و O (V ^ 2) أثناء وقت مصفوفة الجوار. هنا ، يشير E إلى الحواف و V يرمز إلى الرؤوس. يمكن استخدام خوارزمية BFS في الرسم البياني في مجالات مختلفة.
يستخدم BFS بشكل كبير لصياغة كل عقدة مجاورة في اتصالات نظير إلى نظير. تم إنشاء الفهرس بمساعدة هذه التقنية بواسطة برامج الزحف بمحركات البحث. بدءًا من الصفحات المصدر إلى الصفحات الجديدة ، فإنه يساعد في العثور على جميع الروابط المرتبطة. مطلوب للعثور على الأماكن المجاورة بمساعدة مرفق ملاحة GPS. يتم استخدام خوارزمية BFS أثناء بث بعض الحزم في الشبكات. تشمل خوارزمية تحديد المسار BFS. بمساعدة هذه التقنية ، يمكن العثور على أعلى تدفق في الشبكة في خوارزمية Ford-Fulkerson.
ما هو DFS؟
بمساعدة DFS ، يتم اجتياز الرسم البياني بحركة جناح العمق. يتم استخدام المكدس في هذه التقنية ليتم تذكيرك بالحصول على النقطة المجاورة للنقطة السابقة. يتم البحث أثناء حدوث أي تكرار. أثناء شجرة القرار ، يجب إجراء مزيد من التقاطع لزيادة القرار. في الختام ، النصر معترف به. إنه سريع نسبيًا في السرعة من BFS. التعقيد الزمني لـ DFS هو O (V + E) أثناء القائمة المجاورة و O (V ^ 2) أثناء المصفوفة المجاورة. هنا ، يشير E إلى الحواف و V يرمز إلى الرؤوس. يستخدم DFS على نطاق واسع في مختلف المجالات.
عندما يتم تنفيذ DFS على الرسم البياني غير المرجح ، يتم تطوير الحد الأدنى من الأشجار الممتدة لكل زوج من أقصر شجرة مسار. يمكن تطبيقها لتحديد الدورات في الرسوم البيانية. إذا تم العثور على حافة خلفية واحدة في BFS ، فهناك دورة واحدة. يمكن العثور على المسار بين u و v أو رأسين بمساعدة هذه التقنية. تستخدم خوارزمية DFS للفرز الطوبولوجي. يمكن استخدامه لتحديد المكونات المرتبطة بقوة في رسم بياني معين. تُصاغ المكونات لتكون متصلة بقوة عندما يكون هناك مسار بين كل قمة.
الاختلافات الرئيسية بين BFS و DFS
استنتاج
وبالتالي ، يمكن الاستنتاج بالقول أن BFS و DFS يختلفان بشكل واضح عن بعضهما البعض. يتم استخدام BFS في رسم بياني للعثور على أقصر مسار بمساعدة بنية بيانات قائمة الانتظار ويتم استخدام DFS في رسم بياني للعثور على أقصر مسار بمساعدة بنية بيانات المكدس. يختار BFS رأسًا واحدًا أثناء زيارته ويتم وضع علامة عليه بعد ذلك يتم زيارة المجاور وتجميعه في قائمة الانتظار. من ناحية أخرى ، يتم تضمين رؤوس DFS التي تمت زيارتها في المكدس وفي حالة عدم وجود الرؤوس ، يتم ظهور الرؤوس. تعتمد تقنية BFS على قمة الرأس وتستند تقنية DFS على الحافة.
