0-1 BFS باستخدام Deque
أقصر المسارات عندما تكون الأوزان 0 أو 1
0-1 BFS باستخدام Deque درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
نوع خاص من الرسوم البيانية
تحتوي بعض الرسوم البيانية على أوزان حواف تساوي 0 أو 1 فقط. ويمكنك فيها التفوق على Dijkstra باستخدام حيلة أبسط وأسرع.
تعرّف إلى 0-1 BFS
تجد خوارزمية 0-1 BFS أقصر المسارات في الرسوم البيانية ذات الأوزان 0/1 في زمن خطي، من دون كومة أو عامل log على الإطلاق.
الأداة: deque
استبدل الكومة بـ deque، وهو طابور يمكنك الإضافة إليه والإخراج منه من الأمام أو الخلف.
from collections import deque
dq = deque([src])الفكرة الأساسية
تحافظ حافة وزنها 0 على المسافة نفسها، بينما تضيف الحافة ذات الوزن 1 واحدًا إليها. ويحافظ deque على ترتيب المجموعتين كلتيهما.
الأمام للحواف ذات الوزن صفر
عبرت حافة وزنها 0؟ نفّذ appendleft للعقدة المجاورة كي تُعالَج تاليًا، لأنها لا تضيف أي مسافة.
dq.appendleft(v)الخلف للحواف ذات الوزن واحد
عبرت حافة وزنها 1؟ نفّذ append للعقدة المجاورة في الخلف، لأنها تقع في طبقة أبعد بواحد عن المصدر.
dq.append(v)أخرج من الأمام
نفّذ دائمًا popleft للعقدة الحالية. فهذا يحافظ على ترتيب deque حسب المسافة، تمامًا كما يفعل BFS الطبقي.
u = dq.popleft()أرخِ باستخدام الوزن
أرخِ كل حافة: احسب مسافة جديدة تساوي dist[u] مضافًا إليها وزن الحافة، ثم أضف العقدة إلى الأمام أو الخلف وفقًا لذلك الوزن.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndلماذا يبقى مرتبًا
لا يحتوي deque على أكثر من مسافتين مختلفتين في الوقت نفسه. وهذا الثابت هو سبب نجاح الإضافة إلى الأمام أو الخلف.
السرعة الخطية
لعدم وجود كومة، تعمل خوارزمية 0-1 BFS في O(V + E)، وهي أسرع بوضوح من Dijkstra على الرسم البياني نفسه.
متى تستخدمها
استخدمها عندما تكون الانتقالات مجانية أو تكلف واحدًا، مثل الشبكات التي تكون فيها بعض الخطوات محجوبة وأخرى مفتوحة.
اختبار سريع
أرخيت عقدة مجاورة عبر حافة وزنها 0. أين تضعها؟
مراجعة: 0-1 BFS
باستخدام deque، أضف الحواف ذات الوزن 0 إلى الأمام والحواف ذات الوزن 1 إلى الخلف. وستحصل على أقصر المسارات في زمن نظيف قدره O(V+E). ⚡
الأسئلة الشائعة
هل درس «0-1 BFS باستخدام Deque» مجاني؟
نعم — نص درس «0-1 BFS باستخدام Deque» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «0-1 BFS باستخدام Deque»؟
أقصر المسارات عندما تكون الأوزان 0 أو 1 تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «0-1 BFS باستخدام Deque»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Dijkstra باستخدام كومة
- 0-1 BFS باستخدام Deque
- Bellman-Ford والحواف السالبة
- Floyd-Warshall لجميع الأزواج