Pseudo Code
الدرس 4 من 9 في دورة الترتيب الطبوغرافي - خوارزميات المخططات على Coddy.
topologicalSort(n, edges):
build directed adjacency; compute indeg[v] for all v
order = []
repeat n times:
pick = smallest v with indeg[v] == 0 (none left -> stop)
mark pick as used (indeg[pick] = -1)
order.add(pick)
for nb in adj[pick]:
indeg[nb] -= 1
return order- indeg[v] يحسب الحواف الواردة. فقط الحواف
u -> vتضاف إلىindeg[v]. - مسح الرؤوس
0..n-1وأخذ الرأس الأول الذي يمتلك درجة دخول (in-degree) تساوي 0 يعطي أصغر خيار في كل خطوة، لذا يكون الترتيب حتمياً. - ضبط
indeg[pick] = -1هو طريقة بسيطة لتمييز الرأس على أنه تم وضعه بالفعل.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس الترتيب الطبوغرافي - خوارزميات المخططات
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity