Motivation
الدرس 2 من 9 في دورة الترتيب الطبوغرافي - خوارزميات المخططات على Coddy.
لا يوجد الترتيب الطوبولوجي إلا عندما لا يحتوي الرسم البياني على دورات. نقوم ببناء واحد باستخدام خوارزمية كاهن (Kahn's algorithm)، والتي تزيل بشكل متكرر الرأس الذي لا يحتوي على حواف واردة متبقية.
لماذا نتعلم الترتيب الطوبولوجي؟
- الترتيب مع القيود: تعتمد عليه أنظمة البناء، وجدولة المهام، والمتطلبات المسبقة للمواد، وإعادة حساب جداول البيانات.
- اكتشاف الدورات: إذا لم تتمكن من ترتيب كل رأس، فلا بد أن الرسم البياني يحتوي على دورة.
- أساس لخوارزميات DAG: يتم حساب أقصر وأطول المسارات في DAG بالترتيب الطوبولوجي.
يمكن أن توجد العديد من الترتيبات الصالحة. للحصول على إجابة واحدة يمكن التنبؤ بها، نقوم دائمًا بإزالة الرأس الأصغر رقمًا الذي تكون درجته الداخلة (in-degree) هي 0.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
