Implementation (Part 2)
الدرس 6 من 9 في دورة الترتيب الطبوغرافي - خوارزميات المخططات على Coddy.
الآن نقوم بشكل متكرر بإزالة الرؤوس ذات الدرجة الداخلة 0 (in-degree-0) لبناء الترتيب.
التحدي
متوسطالآن قم ببناء الترتيب الكامل.
اكتب دالة باسم topologicalSort تأخذ n ومصفوفة edges المسطحة (موجهة u -> v)، وتعيد ترتيباً طوبولوجياً للرؤوس.
استخدم خوارزمية Kahn: احسب درجات الدخول (in-degrees)، ثم خذ بشكل متكرر أصغر رأس بدرجة دخول 0، وأضفه، وقم بتقليل درجة الدخول لجيرانه الخارجين. المدخلات لهذا التحدي هي رسوم بيانية غير حلقية (acyclic).
أخذ أصغر رأس متاح في كل خطوة يجعل الإجابة فريدة.
جرّب بنفسك
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// اكتب الكود هنا
*returnSize = 0;
return edges;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس الترتيب الطبوغرافي - خوارزميات المخططات
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity