BFS لأقصر المسارات غير الموزونة
حساب المسافة طبقةً بعد طبقة من المصدر
BFS لأقصر المسارات غير الموزونة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما الذي يفعله BFS
يستكشف BFS الرسم البياني على شكل حلقات: يبدأ من نقطة البداية، ثم كل ما يبعد عنها خطوة واحدة، ثم ما يبعد خطوتين، وهكذا. 🌊
لماذا تعني الحلقات أقصر مسار
لأن BFS ينهي كل حلقة قبل الانتقال إلى التالية، فإن أول وصول له إلى عقدة يكون عبر أقصر مسار غير موزون إليها.
الطابور هو المحرّك
يستخدم BFS طابورًا: أول ما يدخل هو أول ما يخرج. تضيف الجيران الجدد إلى الخلف وتعالج العنصر الموجود في المقدمة بعد ذلك.
from collections import deque
q = deque([start])تتبّع ما زرته
احتفظ بعلامة visited حتى لا تضيف العقدة نفسها إلى الطابور مرتين. وهذا يحافظ على سرعة BFS ونهايته.
visited = [False] * (n + 1)
visited[start] = Trueتخزين المسافة
تحتوي مصفوفة dist على طبقة كل عقدة. تبدأ عقدة البداية بالقيمة 0، وتكون مسافة كل جار أكبر بواحد من مسافة والده.
dist = [-1] * (n + 1)
dist[start] = 0إزالة العنصر من المقدمة
في كل خطوة، خذ العقدة الموجودة في مقدمة الطابور. فهي أقرب عقدة لم تُعالج بعد، لذا عالجها الآن.
u = q.popleft()توسيع الجيران
لكل جار للعقدة u لم تتم زيارته، علّمه، واضبط مسافته، ثم أضفه إلى مؤخرة الطابور.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)الحلقة الكاملة
استمر في إزالة العناصر وتوسيعها ما دام الطابور غير فارغ. وعندما يفرغ، تكون قد زرت كل عقدة يمكن الوصول إليها.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)ضع العلامة عند الإضافة إلى الطابور
اضبط visited في اللحظة التي تضيف فيها العقدة إلى الطابور، لا عند إزالتها منه. فوضع العلامة متأخرًا يسمح بتسلل النسخ المكررة إلى الطابور.
تبقى العقد غير القابلة للوصول بقيمة -1
أي عقدة لا تزال مسافتها -1 بعد انتهاء BFS تكون ببساطة غير قابلة للوصول من نقطة البداية. وهذه النتيجة لها دلالتها أيضًا.
BFS خطي التعقيد
يمر BFS على كل عقدة وحافة مرة واحدة، لذلك يعمل بالتعقيد O(n + m). وهذا يكفي بسهولة لتجاوز معظم حدود المسابقات.
تحقق سريع
لماذا يعطي BFS العادي أقصر المسارات؟
مراجعة
تشغّل BFS باستخدام طابور ومصفوفة dist: ضع العلامة عند الإضافة إلى الطابور، ووسّع الجيران، ثم اقرأ أقصر المسافات عند الانتهاء. 🎉
الأسئلة الشائعة
هل درس «BFS لأقصر المسارات غير الموزونة» مجاني؟
نعم — نص درس «BFS لأقصر المسارات غير الموزونة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «BFS لأقصر المسارات غير الموزونة»؟
حساب المسافة طبقةً بعد طبقة من المصدر تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «BFS لأقصر المسارات غير الموزونة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- قوائم التجاور من الإدخال
- BFS لأقصر المسارات غير الموزونة
- DFS والاستدعاء الذاتي والمكدسات التكرارية
- المكوّنات المتصلة والملء الانتشاري