اكتشاف الدورات في الرسوم البيانية الموجّهة
تلوين العقد للعثور على الحواف الراجعة
اكتشاف الدورات في الرسوم البيانية الموجّهة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
لماذا تهم الدورات
تعني الدورة الموجّهة أن التبعيات تعود إلى نفسها في حلقة. ويخبرك اكتشافها بأنه لا يمكن إنشاء ترتيب طوبولوجي أو جدول زمني صالح.
الموجّه يختلف عن غير الموجّه
يعتمد اكتشاف الدورة هنا على الاتجاه. فاتباع الأضلاع في الاتجاه الخاطئ لا يُحتسب، ولذلك لا تنطبق حيل الرسوم غير الموجّهة.
فكرة الألوان الثلاثة
امنح كل عقدة أحد ثلاثة ألوان: الأبيض يعني أنه لم تتم زيارتها، والرمادي يعني أن معالجتها جارية، والأسود يعني أنها اكتملت بالكامل.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nالرمادي يعني وجودها في المكدس
توجد العقدة الرمادية في مسار DFS الحالي. لقد دخلت إليها، لكنك لم تنتهِ بعد من استكشاف جميع ذرياتها.
ادخل إلى عقدة
عندما تصل DFS إلى عقدة، لوّنها بالرمادي قبل الاستكشاف. بذلك تحدد أنها جزء من المسار النشط.
def dfs(u):
color[u] = GRAYإشارة الضلع الراجع
إذا وصلت إلى جار لونه رمادي بالفعل، فقد وجدت ضلعًا راجعًا إلى المسار الحالي. وهذا يعني وجود دورة.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleكرّر داخل العقدة البيضاء
الجار الأبيض جديد، لذا نفّذ التكرار داخله. أعد القيمة True فورًا إذا أبلغ أي استدعاء أعمق عن وجود دورة.
elif color[v] == WHITE and dfs(v):
return Trueالأسود آمن
الجار الأسود استُكشف بالكامل وثبت خلوّه من الدورات، لذا يمكنك تجاهله. فإعادة زيارته لن تؤدي إلا إلى إضاعة الوقت.
أنه العقدة
بعد التعامل مع جميع الجيران، لوّن العقدة بالأسود. بذلك تغادر المسار النشط وتُعلَّم بأنها اكتملت.
color[u] = BLACK
return Falseغطِّ كل مكوّن
قد يكون الرسم البياني غير متصل، لذا ابدأ DFS من كل عقدة لا تزال بيضاء، للتأكد من فحص الرسم بأكمله.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')انتبه إلى حد التكرار
قد تتسبب الرسوم البيانية العميقة في تجاوز مكدس التكرار الخاص بـ Python. ارفع الحد أو أعد كتابة DFS باستخدام مكدس صريح.
import sys
sys.setrecursionlimit(300000)تحقق سريع
أثناء تنفيذ DFS، وصلت إلى جار لونه رمادي حاليًا. ماذا وجدت للتو؟
مراجعة: اكتشاف الدورات
لوّن العقد بالأبيض ثم الرمادي ثم الأسود. وجود جار رمادي أثناء DFS يعني وجود ضلع راجع، وهذا يثبت وجود دورة موجّهة. 🔁
الأسئلة الشائعة
هل درس «اكتشاف الدورات في الرسوم البيانية الموجّهة» مجاني؟
نعم — نص درس «اكتشاف الدورات في الرسوم البيانية الموجّهة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «اكتشاف الدورات في الرسوم البيانية الموجّهة»؟
تلوين العقد للعثور على الحواف الراجعة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «اكتشاف الدورات في الرسوم البيانية الموجّهة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الترتيب الطوبولوجي بخوارزمية Kahn
- اكتشاف الدورات في الرسوم البيانية الموجّهة
- المكوّنات شديدة الاتصال
- الجسور ونقاط المفصل