BFS لأقصر المسارات غير الموزونة
حساب المسافة طبقةً بعد طبقة من المصدر
BFS لأقصر المسارات غير الموزونة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 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) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «BFS لأقصر المسارات غير الموزونة»؟
حساب المسافة طبقةً بعد طبقة من المصدر تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «BFS لأقصر المسارات غير الموزونة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- قوائم التجاور من الإدخال
- BFS لأقصر المسارات غير الموزونة
- DFS والاستدعاء الذاتي والمكدسات التكرارية
- المكوّنات المتصلة والملء الانتشاري