يمكن وصف الخوارزمية على النحو التالي:
إعطاء رسم بياني موجه برؤوس n وحواف m. مطلوب إعادة ترقيم رؤوسها بطريقة تؤدي بها كل حافة من قمة ذات رقم أقل إلى قمة ذات رأس أعلى.
بعبارة أخرى ، مطلوب إيجاد تبديل للرؤوس (ترتيب طوبولوجي) يتوافق مع الترتيب الذي تقدمه جميع حواف الرسم البياني.
سنستخدم بحث العمق أولاً (dfs (v))
إذا أضفنا رأسنا إلى بداية القائمة وقت الخروج من & nbsp؛ \ (dfs (v) \) & nbsp ؛، ثم في النهاية في هذه القائمة تحصل على تصنيف طوبولوجي.
وهكذا ، النوع الطوبولوجي المطلوب & [مدش] ؛ يتم ترتيب ذلك بترتيب تنازلي لأوقات الخروج.
|