DFS (اجتياز العمق الأول) في بنية البيانات: ما المقصود بالترتيب والتطبيقات

معنى DFS في بنية البيانات

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

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

الخوارزمية

قم بصياغة دالة تكرارية تأخذ فهرس العقدة وصفيف تمت زيارته.

1. احتفظ بالعقدة الحالية على أنها تمت زيارتها ثم اطبعها.
2. اجتياز جميع الملاحظات المجاورة وتلك غير المميزة واستدعاء الوظيفة العودية بفهرس العقدة المجاورة.

استكشف دوراتنا التدريبية الشهيرة في هندسة البرمجيات

الخصائص

يختلف تحليل الزمان والمكان في DFS في بنية البيانات وفقًا لمجال تطبيقه. من الناحية النظرية ، يتم استخدام DFS بشكل أساسي لعبور رسم بياني كامل ويستغرق وقتًا O (| V | + | E |) حيث | V | يصور عدد الرؤوس و | E | يصور عدد الحواف. هذا الرسم البياني خطي.

في هذه التطبيقات ، يتم استخدام space O (| V |) أيضًا كملاذ أخير للحفاظ على مجموعة الرؤوس مخزنة في مسار البحث ومجموعة القمم التي تمت زيارتها بالفعل. لذلك ، يكون إعداد حدود الوقت والمساحة مشابهًا لبحث العرض الأول. هنا ، الخوارزميتان المستخدمتان أقل اعتمادًا على تعقيدهما وأكثر اعتمادًا على الخصائص المختلفة لأوامر الرأس التي تنتجها الخوارزميتان.

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

ومع ذلك ، تذكر أن هذا الرقم ليس له نفس حجم الرسم البياني بأكمله نظرًا لأن بعض الرؤوس قد يتم البحث عنها عدة مرات بينما لا يتم البحث في البعض الآخر.

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

تعلم دورات تطوير البرمجيات عبر الإنترنت من أفضل الجامعات في العالم. اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.

خوارزمية العمق أولا البحث

يتم تقسيم كل رأس من الرسم البياني في تنفيذ DFS القياسي إلى أي من فئتين:

1. لم تتم زيارتها
2. تمت زيارته

يتم استخدام الخوارزمية لتحديد كل قمة وتمييزها على أنها تمت زيارتها وفي نفس الوقت تجنب الدورات.

هذه هي الطريقة التي تعمل بها خوارزمية DFS:

1. ضع أي رأس معين للرسم البياني على مكدس.
2. يجب إضافة العنصر الموجود أعلى المكدس إلى القائمة التي تمت زيارتها.
3. قم بعمل قائمة بالعقد المجاورة لتلك القمة وأضف تلك غير الموجودة في القائمة التي تمت زيارتها أعلى المكدس.
4. استمر في تكرار الخطوات السابقة حتى يفرغ المكدس.

طلب DFS

ترتيب الرأس: هناك أربع طرق للترتيب الخطي لرؤوس الرسم البياني أو الشجرة في DFS:

1. تُعرف قائمة الرؤوس المرتبة كيف تمت زيارتها أولاً بواسطة خوارزمية DFS بالطلب المسبق. إنها طريقة موجزة لوصف تقدم البحث.
2. تُعرف قائمة الرؤوس بالترتيب الذي تمت زيارته مؤخرًا بواسطة الخوارزمية باسم الترتيب اللاحق.
3. قائمة الرؤوس بالترتيب المعاكس لزيارتهم الأولى هي ترتيب مسبق عكسي. لذلك ، لا ينبغي الخلط بينه وبين طلب آخر.
4. قائمة الرؤوس بالترتيب المعاكس لزيارتهم الأخيرة هي ترتيب لاحق عكسي. لا ينبغي أن يكون مخطئًا للطلب المسبق.

بالإضافة إلى ذلك ، يوجد ترتيب وترتيب عكسي للأشجار الثنائية.

عمق البحث الأول أو DFS للرسم البياني

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

إخراج بحث العمق الأول

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

تطبيقات اجتياز العمق الأول (DFS)

يُستخدم بحث العمق أولاً في الخوارزميات التالية كعنصر أساسي:

• البحث عن المكونات المتصلة.
• إيجاد مكونات متصلة 2- (قمة أو حافة).
• إيجاد جسور الرسم البياني.
• إيجاد مكونات متصلة 3- (قمة أو حافة).
• الفرز الطوبولوجي.
• إيجاد المكونات التي ترتبط بقوة.
• معرفة ما إذا كان النوع مشابهًا لنوع أو آخر في شجرة النشوء والتطور.
• اختبار الاستواء.
• إنتاج كلمات لتحديد مجموعة حدود أي مجموعة.
• حل الألغاز التي لها حل واحد فقط ، مثل المتاهات.
• جيل المتاهة .
• البحث عن اتصال ثنائي في الرسوم البيانية.

DFS Pseudocode والتنفيذ في Python

يتم تشغيل وظيفة init () على كل عقدة في الكود الكاذب أدناه للتأكد من زيارة جميع الرؤوس. هذا مهم بشكل خاص حيث قد تحتوي الرسوم البيانية على مناطق مختلفة غير متصلة.

هنا هو الكود الكاذب:

DFS (G ، u)

u.visited = صحيح

لكل v ∈ G.Adj [u]

إذا تمت الزيارة == خطأ

DFS (G ، v)

فيه() {

لكل u ∈ G

u.visited = false

لكل u ∈ G

DFS (G ، u)

}

إليك تطبيق DFS في Python:

الرسم البياني = {

'5': ['3 ′،' 7 ']،

'2': ['1'، '3']،

"6": ["7"]،

"3": []،

"4": ["6"]،

"7": []

}

تمت زيارتها = مجموعة ()

def dfs (تمت زيارتها ، رسم بياني ، عقدة):

إذا لم تتم زيارة العقدة:

طباعة (عقدة)

زار.إضافة (عقدة)

للجار في الرسم البياني [عقدة]:

dfs (تمت زيارتها ، رسم بياني ، جار)

طباعة ("هذا هو DFS:")

dfs (تمت الزيارة ، رسم بياني ، "5")

انتاج:

هذا هو DFS: 5

استكشف دوراتنا التدريبية الشهيرة في هندسة البرمجيات

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

استكشف جون ريف التعقيد الحسابي لـ Depth First Search. لكي نكون دقيقين ، في الرسم البياني ، فإن الحقيقة المعينة هي G ، دع O يكون الترتيب القياسي الذي تحدده خوارزمية DFS المتكررة. يمثل G الرسم البياني ، ويمثل O إخراج الطلب لخوارزمية DFS الزائدة. يُعرف هذا الإخراج بترتيب DFS المعجمي.

استنتاج

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

لدى upGrad بعض دورات DFS عالية المستوى مثل ماجستير العلوم في علوم الكمبيوتر والتخصص في البيانات الضخمة .

إذا كنت تكافح لاتخاذ خطوتك التالية وتبحث عن بعض مشورة الخبراء ، فإن upGrad Mentorship تسعى لتزويدك بجلسات فردية مع أفضل المستشارين والخبراء المهنيين في هذا المجال.