الترتيب الطوبولوجي بخوارزمية Kahn
ترتيب المهام التي تعتمد على غيرها
الترتيب الطوبولوجي بخوارزمية Kahn درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ما هو الترتيب الطوبولوجي
يسرد الترتيب الطوبولوجي كل عقدة في رسم بياني موجّه بحيث يشير كل ضلع من عقدة أسبق إلى عقدة لاحقة. فكّر في المهام التي يجب إنجازها قبل المهام التي تعتمد عليها.
يُسمح فقط بالرسوم DAG
ينجح هذا فقط مع DAG، أي رسم بياني موجّه لا دوري. إذا وُجدت دورة، فلن يوجد ترتيب صالح يحقق كل تبعية.
فكرة الدرجة الداخلة
تعتمد خوارزمية Kahn على الدرجة الداخلة: عدد الأضلاع التي تشير إلى عقدة. العقدة ذات الدرجة الداخلة الصفرية لا تملك تبعيات غير مستوفاة.
احسب كل درجة داخلة
في المرور الأول، افحص كل الأضلاع واحسب عدد المرات التي تكون فيها كل عقدة وجهة. يمنحك ذلك الدرجة الداخلة لكل عقدة.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1هيّئ قائمة انتظار العقد الجاهزة
كل عقدة ذات درجة داخلة صفرية جاهزة فورًا، لذا أضفها كلها إلى قائمة انتظار لبدء المعالجة.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)عالج عقدة واحدة
أخرج عقدة جاهزة من قائمة الانتظار وأضفها إلى ترتيبك. فهي آمنة الآن لأن لا شيء متبقّي يعتمد عليها.
u = q.popleft()
order.append(u)حرّر جيرانها
لكل جار، أنقص درجته الداخلة بمقدار واحد. عندما يصل الجار إلى الصفر، يصبح جاهزًا وينضم إلى قائمة الانتظار.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)كرّر حتى تفرغ القائمة
واصل الإخراج وتحرير الجيران حتى تفرغ قائمة الانتظار. ينمو الترتيب بإضافة عقدة آمنة في كل مرة، حتى تُضاف جميع العقد.
اكتشف الدورة مجانًا
إذا كان ترتيبك النهائي يحتوي على عدد عقد أقل من n، فقد احتجزت دورة بقية العقد. تمنحك خوارزمية Kahn اكتشاف الدورات دون تكلفة إضافية.
if len(order) < n:
print('cycle exists')زمن التنفيذ
تُفحص كل عقدة وكل ضلع مرة واحدة، لذلك تعمل خوارزمية Kahn بتعقيد O(V + E). وهذا يناسب الرسوم البيانية التي تحتوي على ملايين الأضلاع.
ترتيبات صالحة متعددة
عندما تكون عدة عقد جاهزة في الوقت نفسه، يمكن اختيار أيٍّ منها تاليًا. لذلك غالبًا ما يملك DAG ترتيبات طوبولوجية عديدة صالحة، وليس ترتيبًا واحدًا فقط.
تحقق سريع
أنهيت خوارزمية Kahn، لكن الترتيب يحتوي على عدد عقد أقل من n. ماذا يعني ذلك؟
مراجعة: خوارزمية Kahn
احسب الدرجات الداخلة، وأضف العقد ذات الدرجة الصفرية إلى قائمة الانتظار، ثم أخرج عقدة وأنقص درجات جيرانها وكرّر. هذا هو الفرز الطوبولوجي بطريقة واضحة، بتعقيد O(V+E). 🚀
الأسئلة الشائعة
هل درس «الترتيب الطوبولوجي بخوارزمية Kahn» مجاني؟
نعم — نص درس «الترتيب الطوبولوجي بخوارزمية Kahn» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «الترتيب الطوبولوجي بخوارزمية Kahn»؟
ترتيب المهام التي تعتمد على غيرها تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «الترتيب الطوبولوجي بخوارزمية Kahn»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الترتيب الطوبولوجي بخوارزمية Kahn
- اكتشاف الدورات في الرسوم البيانية الموجّهة
- المكوّنات شديدة الاتصال
- الجسور ونقاط المفصل