الترتيب الطوبولوجي

في كل مرة تثبّت فيها برنامجًا أو تبني تطبيقًا أو تخطط لمشروع، لا بد أن يحدد شيء ما ما يُفعل أولاً. إذا كانت المهمة B تحتاج إلى المهمة A، فيجب أن تأتي A أبكر. والترتيب الطوبولوجي يحوّل شبكة من هذه القواعد إلى خط مستقيم واحد.

رسم بياني لعقد تربطها أسهم أحادية الاتجاه، العقد الموضوعة باللون الأخضر، والترتيب حتى الآن مرسوم صفًا في الأسفل
رسم بياني لعقد تربطها أسهم أحادية الاتجاه، العقد الموضوعة باللون الأخضر، والترتيب حتى الآن مرسوم صفًا في الأسفل

الفكرة

ارسم كل مهمة عقدةً وكل قاعدة «A قبل B» سهمًا من A إلى B. الترتيب الطوبولوجي صف يضم كل العقد ويشير فيه كل سهم إلى اليمين. ويُسمى ترتيبًا لأنه يضع الأشياء في تسلسل، لكنه بخلاف ترتيب الأعداد لا يلتزم إلا بالأسهم: فالعقد التي لا تربطها سلسلة من الأسهم يمكن أن تأتي بأي ترتيب.

متى يكون مستحيلاً

إذا كوّنت الأسهم دورة، كأن تكون A قبل B، وB قبل C، وC قبل A، فيجب أن تأتي A قبل نفسها. لذلك يوجد الترتيب الطوبولوجي تمامًا حين لا يحتوي الرسم البياني على دورة موجهة. ويُسمى رسم كهذا رسمًا بيانيًا موجهًا لا دوريًا، أو DAG. والطريقتان أدناه تجدان الدورة إن وُجدت، فهما أيضًا اختبار مفيد للدورات.

مثال

خذ الأسهم A → C، وB → C، وB → D، وC → E، وD → E. تعدّ خوارزمية كان الأسهم الداخلة: لا شيء لـA وB، فتأتي A أولاً ثم B. وحذف أسهم B يحرر C وD فتتبعانها، ثم E: الترتيب A, B, C, D, E. وتزور طريقة DFS العقدة A ثم C ثم E؛ فتنتهي E أولاً، ثم C، ثم A، وتذهب كل منها إلى المقدمة. ثم تزور B وD، فتنتهيان وتوضعان أمامها: الترتيب B, D, A, C, E. والترتيبان كلاهما صحيح.

كان أم DFS؟

خوارزمية كان، التي نشرها Arthur Kahn عام 1962، تعمل إلى الأمام: فهي تعرف دائمًا أي المهام يمكن أن تبدأ الآن، وهذا يناسب الجدولة، ويمكنها الاختيار بين المهام الحرة بأي قاعدة، كالترتيب الأبجدي. أما طريقة DFS، التي نشرها Robert Tarjan على نطاق واسع عام 1976، فتعمل إلى الخلف من النهايات ولا تحتاج إلا إلى بحث بالعمق أولاً. وفي كلتيهما يزداد الوقت مع عدد العقد مضافًا إليه عدد الحواف.

روبرت تارجان، الذي أظهر مع جون هوبكروفت في 1972–73 أن البحث بالعمق أولاً يحل كثيراً من مسائل الرسوم في زمن خطي؛ ونالا جائزة تورنغ عام 1986 جزئياً عن ذلك العمل.
روبرت تارجان، الذي أظهر مع جون هوبكروفت في 1972–73 أن البحث بالعمق أولاً يحل كثيراً من مسائل الرسوم في زمن خطي؛ ونالا جائزة تورنغ عام 1986 جزئياً عن ذلك العمل.

الاستخدامات

أدوات البناء مثل make تترجم الملفات بعد الملفات التي تعتمد عليها. ومديرو الحزم يثبّتون المكتبات بترتيب الاعتماديات. وجداول البيانات تعيد حساب الخلية بعد الخلايا التي تستخدمها صيغتها. والجامعات تتحقق من إمكان استيفاء المتطلبات السابقة للمقررات، والمترجمات ترتب التعليمات، وخطوط معالجة البيانات تشغّل كل خطوة بعد أن تجهز مدخلاتها. وأمر Unix المسمى tsort يجري ترتيبًا طوبولوجيًا بنفسه.

استكشفه

افتح التطبيق واضغط «خطوة». تبيّن الأسهم أي عقدة يجب أن تأتي قبل أيها. مع خوارزمية كان، يعدّ الرقم على كل عقدة أسهمها الداخلة المتبقية، والعقد الحرة زرقاء. ومع طريقة DFS، العقد الزرقاء قيد الزيارة والخضراء موضوعة. ويكبر الترتيب في الصف أسفل الرسم البياني. فعّل «أضف دورة» وشاهد الطريقتين تكتشفان أنه لا يوجد ترتيب.

الأسئلة المتداولة

ماذا تعني كلمة طوبولوجي هنا؟

يأتي الاسم من الطوبولوجيا، وهي دراسة كيفية اتصال الأشياء لا شكلها الدقيق. فالترتيب يعتمد فقط على العقد التي تربطها الأسهم، لا على مكان رسمها.

كيف أجد الدورة حين لا يوجد ترتيب؟

تُظهرها طريقة DFS مباشرة: الحافة إلى عقدة ما زالت قيد الزيارة، مع مسار العقد قيد الزيارة، هي الدورة. أما خوارزمية كان فتخبرك فقط بالعقد العالقة؛ والبحث بينها يجد الدورة.

هل يمكنني اختيار ترتيب معيّن من بين الترتيبات الصحيحة؟

نعم. في خوارزمية كان، حين تكون عدة عقد حرة، اختر ما تفضله منها، كأصغر تسمية أو أكثر المهام إلحاحًا. واستخدام طابور الأولوية يعطي الترتيب الذي يأتي أولاً أبجديًا.

كيف يُستخدم الترتيب الطوبولوجي مع أقصر المسارات؟

في رسم بياني موجه لا دوري، يؤدي إرخاء حواف كل عقدة بالترتيب الطوبولوجي إلى إيجاد كل أقصر المسارات من بداية واحدة في مرور واحد، حتى مع الحواف السالبة، وأسرع من ديكسترا أو بلمان–فورد.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب الترتيب الطوبولوجي