DFS والاستدعاء الذاتي والمكدسات التكرارية
الاستكشاف بعمق وتجنب حدود الاستدعاء الذاتي
DFS والاستدعاء الذاتي والمكدسات التكرارية درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ما الذي يفعله DFS
يتعمق DFS قدر الإمكان في مسار واحد، ثم يعود إلى الخلف ويجرب المسار التالي. تخيله كاستكشاف ممرات متاهة ممرًا بعد آخر. 🧭
DFS مقابل BFS
ينتشر BFS على شكل حلقات، بينما يتعمق DFS أولًا. يزور كلاهما كل عقدة يمكن الوصول إليها، لكن بترتيب مختلف تمامًا.
البنية التكرارية
يضع DFS التكراري علامة visited على العقدة، ثم يستدعي نفسه لكل جار لم تتم زيارته. وتحتفظ مكدس الاستدعاءات بموضع العودة.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)ضع العلامة قبل الاستدعاء التكراري
اضبط visited عند دخول العقدة، قبل استكشاف الجيران. وإلا فستدفع الدورات DFS إلى تكرار لا نهائي.
فخ حد الاستدعاء التكراري
تضع Python حدًا للتكرار قريبًا من 1000 استدعاء. ويتسبب الرسم البياني العميق في ظهور RecursionError، الذي يظهر بوصفه حكمًا بخطأ وقت التشغيل.
رفع الحد
أحد الحلول السريعة هو رفع الحد باستخدام setrecursionlimit. اضبطه على قيمة تتجاوز أسوأ عمق متوقع قبل تشغيل DFS.
import sys
sys.setrecursionlimit(300000)استخدم الطريقة التكرارية بدلًا من ذلك
الحل الأكثر أمانًا هو استخدام DFS تكراري مع مكدس خاص بك. فعند عدم وجود عمق لاستدعاءات الدوال، لن يحدث انهيار بسبب التكرار أبدًا.
stack = [start]إزالة العنصر من المكدس
في كل خطوة، أزل العنصر الموجود أعلى المكدس. ويجعل ترتيب الداخل أخيرًا يخرج أولًا DFS يتعمق في أحدث مسار أولًا.
u = stack.pop()إضافة الجيران إلى المكدس
بعد إزالة u، أضف كل جار لم تتم زيارته إلى المكدس. ضع علامة عليها حتى لا تضيفها مرة أخرى.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)الحلقة التكرارية الكاملة
كرّر الإزالة والإضافة ما دام المكدس يحتوي على عقد. وعندما يفرغ، تكون قد زرت كل عقدة يمكن الوصول إليها.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)التكلفة نفسها مثل BFS
مثل BFS، يزور DFS كل عقدة وحافة مرة واحدة، لذلك يعمل بالتعقيد O(n + m). اختر الخوارزمية وفق الترتيب الذي يناسب المهمة.
تحقق سريع
ينهار DFS التكراري الخاص بك على رسم بياني عميق. لماذا؟
مراجعة
تشغّل DFS تكراريًا أو باستخدام مكدسك الخاص، وتضع علامة الزيارة عند الدخول، وتنتقل إلى الطريقة التكرارية عندما يصبح الرسم البياني عميقًا. 🎉
الأسئلة الشائعة
هل درس «DFS والاستدعاء الذاتي والمكدسات التكرارية» مجاني؟
نعم — نص درس «DFS والاستدعاء الذاتي والمكدسات التكرارية» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «DFS والاستدعاء الذاتي والمكدسات التكرارية»؟
الاستكشاف بعمق وتجنب حدود الاستدعاء الذاتي تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «DFS والاستدعاء الذاتي والمكدسات التكرارية»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- قوائم التجاور من الإدخال
- BFS لأقصر المسارات غير الموزونة
- DFS والاستدعاء الذاتي والمكدسات التكرارية
- المكوّنات المتصلة والملء الانتشاري