موضوعة
تنتظر وضعها
الحواف المفحوصة

  • الحالية
  • حرة أو قيد الزيارة
  • موضوعة
  • دورة

مزيد عن الترتيب الطوبولوجي

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

الجوارب قبل الحذاء، والأساسات قبل الجدران، والمقرر قبل المقرر الذي يحتاج إليه. يضع الترتيب الطوبولوجي عقد رسم بياني حوافه أحادية الاتجاه في صف تشير فيه كل حافة إلى الأمام. اختر خوارزمية كان أو طريقة DFS وتقدّم خطوة بخطوة لترى الترتيب يكبر، وأضف دورة لترى لماذا يصبح أي ترتيب مستحيلاً عندئذ. اضغط «تشغيل» لمشاهدة الترتيب وهو يكبر، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. كل حافة أحادية الاتجاه كما يبيّن سهمها: اعتبرها تعني «هذا يأتي قبل ذاك». اختر الطريقة: تضع خوارزمية كان أولاً العقد التي لا تدخلها حواف، والرقم على كل عقدة هو عدد الحواف الداخلة التي ما زالت لها؛ وتضع طريقة DFS كل عقدة في المقدمة بعد أن يوضع كل ما يأتي بعدها. الصف أسفل الرسم البياني هو الترتيب حتى الآن. فعّل «أضف دورة» لترى كيف تكتشف كل طريقة الدورة. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

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

خوارزمية كان

عُدّ لكل عقدة الحواف التي تشير إليها. العقدة التي لا تدخلها حواف لا تعتمد على شيء، فيمكن أن تأتي أولاً. ضع عقدة كهذه، واحذف حوافها الخارجة: فتنقص العقد التي كانت تشير إليها حافةً داخلة واحدة، وقد يصل بعضها إلى الصفر فيصبح حرًا. واصل وضع العقد الحرة حتى لا يبقى منها شيء. فإن بقيت عقد لم تتحرر قط، فهي تنتظر بعضها بعضًا في دورة، ولا يوجد ترتيب طوبولوجي.

طريقة DFS

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

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

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

ترتيب لعقد رسم بياني موجه تذهب فيه كل حافة من عقدة سابقة إلى عقدة لاحقة. وإذا كانت الحواف تعني «يجب أن يأتي قبل»، فهو ترتيب يمكن فيه إنجاز كل المهام.

متى يوجد ترتيب طوبولوجي؟

تمامًا حين لا يحتوي الرسم البياني على دورة موجهة: أي حين يكون رسمًا بيانيًا موجهًا لا دوريًا، أو DAG. ومع وجود دورة، يجب أن تأتي كل عقدة عليها قبل نفسها.

هل الترتيب الطوبولوجي فريد؟

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

ما سرعة الترتيب الطوبولوجي؟

تنظر الطريقتان إلى كل عقدة وكل حافة عددًا ثابتًا من المرات، فيزداد العمل مع عدد العقد مضافًا إليه عدد الحواف.

هل يُرسل الرسم البياني إلى أي مكان؟

لا. يُنشأ الرسم البياني ويُرتَّب داخل متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.

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

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

الانتقال إلى المحرر