اجتياز الرسم البياني الموجه الدوري

Question

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

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

قبل أن أحاول كتابة خوارزمية O (n^3) الخاصة بي ، هل يمكن لأي شخص أن يوجهني إلى حل مناسب؟ و ماذا هو هذه المشكلة بالذات تسمى؟

Answer 1

نظرًا لأن الرسم البياني دوري (يمكن أن يحتوي IE على دورات) ، فسأقوم أولاً بتقسيمه إلى مكونات متصلة بقوة. أ مكون متصل بقوة من الرسم البياني الموجه هو خريطة فرعية حيث يمكن الوصول إلى كل عقدة من كل عقدة أخرى في نفس الرسم الفرعي. هذا من شأنه أن يسفر عن مجموعة من الخراطيم الفرعية. لاحظ أن مكونًا متصلاً بقوة لأكثر من عقدة واحدة هو دورة فعالة.

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

تتمثل الخطوة التالية في انهيار كل مكون متصل بقوة في عقدة واحدة. نظرًا لأن العقد داخل نفس المكون لها نفس البيانات ، وبالتالي فهي متشابهة بشكل أساسي ، فإن هذه العملية لا تغير الرسم البياني حقًا. سترث "Super Node" الذي تم إنشاؤه حديثًا جميع الحواف التي تخرج أو تأتي إلى العقد المكون من العقد خارج المكون.

نظرًا لأننا قد انهارنا جميع المكونات المتصلة بقوة ، فلن تكون هناك دورات في الرسم البياني الناتج (لماذا؟ لأنه لو كانت هناك دورة تتشكل من العقد الناتجة ، فقد تم وضعها جميعًا في نفس المكون في المقام الأول). الرسم البياني الناتج الآن أ إخراج الرسم البياني الحشيش. لا توجد دورات ، وعمقًا بسيطًا ، عبورًا بسيطًا من جميع العقد مع endegree = 0 (أي العقد التي لا تحتوي على حواف واردة) ، يجب أن تنجز البيانات من كل عقدة إلى العقد المجاورة (أي "أطفالها") .