هل هناك خوارزمية مناسبة لحل مشكلة إزالة الحواف؟

Question

يوجد رسم بياني موجه (غير متصل بالضرورة) يتم تمييز عقدة واحدة أو أكثر منه كمصادر.أي عقدة يمكن الوصول إليها من أي مصدر تعتبر "مضاءة".لنفترض الآن أنه تمت إزالة إحدى الحواف.المشكلة هي تحديد العقد التي كانت مضاءة سابقًا ولم تعد مضاءة.

أفترض أنه يمكن النظر في تشبيه مثل نظام كهرباء المدينة.

Answer 1

وهذا هو "دينامية الرسم البياني وسائل الأتصال" المشكلة. وينبغي أن يكون ورقة التالية مفيدة:

<م> خوارزمية وسائل الأتصال الحيوي بشكل كامل لمخطط موجه مع وقت التحديث الخطي تقريبا. يام Roditty، أوري زويك. نظرية الحاسبات 2002.

وهذا يعطي خوارزمية مع O (م * الجذر التربيعي (ن)) - التحديثات في الوقت (<م> إطفاء ) وO (الجذر التربيعي (ن)) - الاستفسارات الوقت على الرسم البياني ربما-دوري (حيث m هو عدد من حواف و n عدد العقد). إذا كان الرسم البياني احلقي، وهذا يمكن أن تحسن إلى O (م) التحديثات -Time (<م> إطفاء ) وO (ن / سجل ن) الاستفسارات -Time.

وانها دائما ممكن هل يمكن أن نفعل ما هو أفضل من ذلك نظرا للبنية محددة لمشكلتك، أو عن طريق الفضاء التداول لهذا الوقت.

Answer 2

إذا بدلا من مجرد "مضاءة" أو "غير المضاءة" التي من شأنها أن تبقي مجموعة من العقد الذي هو مدعوم من عقدة أو مضاءة، والنظر في عقدة مع مجموعة فارغة بأنها "غير المضاءة" وعقدة مع غير فارغة النحو "مضاءة"، ثم إزالة ميزة ببساطة تنطوي على إزالة عقدة المصدر من مجموعة العقدة الهدف.

وتحرير: نسيت هذا: وإذا قمت بإزالة آخر مضاءة من عقدة في المجموعة، واجتياز حواف وإزالة العقدة أنت فقط "مظلمة" من مجموعتهم (وربما اجتياز من هناك أيضا، وهلم جرا)

وEDIT2 (إعادة صياغة لتافا): أولا: أنا أخطأت السؤال الأصلي، ويعتقد أنه ذكر أن كان معروفا لكل عقدة بالفعل لتكون مضاءة أو غير المضاءة، والتي كما أنا أعيد قراءتها الآن، لم يذكر

ولكن، إذا كان كل عقدة في الشبكة قمت بتخزين مجموعة تحتوي على العقد كانت مضاءة من خلال، يمكنك اجتياز بسهولة الرسم البياني من على حافة إزالة وإصلاح عن أي إشارات مضاءة / مظلمة. هكذا على سبيل المثال إذا كان لدينا العقد A، B، C، D مثل هذا: (محاولة عرجاء في الفن أسكي)

A -> B >- D
 \-> C >-/

وبعد ذلك في العقدة A كنت تخزين أنه كان المصدر (وبالتالي مضاءة في حد ذاته)، وفي كل من B و C كنت تخزين كانوا مضاءة بواسطة A، وD كنت تخزين التي كانت مضاءة من قبل على حد سواء A و C.

وبعد ذلك نقول اننا إزالة حافة من B إلى D: D ونحن إزالة B من مضاءة مصدر القائمة، لكنها لا تزال مضاءة كما لا تزال مضاءة من قبل A. التالي القول أننا إزالة حافة من A إلى C بعد تتم إزالة من مجموعة C، وبالتالي C لم يعد مضاءة: أن نحن ثم انتقل إلى اجتياز حواف التي نشأت في C، C وإزالة من مجموعة D'الصورة التي هي الآن أيضا غير المضاءة. في هذه الحالة نحن القيام به، ولكن إذا كان مجموعة أكبر، كنا نذهب فقط على من D.

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

Answer 3

هل هذا واجبك المنزلي؟

الحل الأبسط هو إجراء DFS (http://en.wikipedia.org/wiki/Depth-first_search) أو BFS (http://en.wikipedia.org/wiki/Breadth-first_search) على الرسم البياني الأصلي بدءًا من العقد المصدر.سيؤدي هذا إلى حصولك على جميع العقد المضيئة الأصلية.

الآن قم بإزالة الحافة المعنية.قم بعمل DFS مرة أخرى.يمكنك العقد التي لا تزال مضاءة.

قم بإخراج العقد التي تظهر في المجموعة الأولى وليس الثانية.

هذه خوارزمية مثالية غير مقاربة، نظرًا لأنك تقوم بعمل اثنين من DFSs (أو BFSs) التي تأخذ O(n + m) مرات ومساحة (حيث n = عدد العقد، m = عدد الحواف)، والتي تهيمن على التعقيد.تحتاج إلى وقت ومساحة o(n + m) على الأقل لقراءة المدخلات، وبالتالي فإن الخوارزمية هي الأمثل.

الآن إذا كنت تريد إزالة عديد الحواف، والتي من شأنها أن تكون مثيرة للاهتمام.في هذه الحالة، سنتحدث عن هياكل البيانات الديناميكية.هل هذا ما قصدته؟

يحرر:مع الأخذ بعين الاعتبار التعليقات:

• لا يمثل عدم الاتصال مشكلة، حيث لن يتم الوصول إلى العقد الموجودة في المكونات المتصلة التي لا يمكن الوصول إليها أثناء البحث
• هناك طريقة ذكية لإجراء DFS أو BFS من جميع العقد مرة واحدة (سأصف BFS).عليك فقط وضعها جميعًا في البداية على المكدس/قائمة الانتظار.

كود زائف لـ BFS يبحث عن جميع العقد التي يمكن الوصول إليها من أي عقدة البداية:

Queue q = [all starting nodes]
while (q not empty)
{
   x = q.pop()
   forall (y neighbour of x) {
      if (y was not visited) {
         visited[y] = true
         q.push(y)
      }
   }
}

استبدل قائمة الانتظار بالمكدس وستحصل على نوع من DFS.

Answer 4

وكيف كبيرة وكيف يتم توصيل الرسوم البيانية؟ هل يمكن تخزين جميع المسارات من العقد المصدر إلى كافة العقد الأخرى وابحث عن العقد حيث تحتوي على كافة المسارات إلى أن عقدة واحدة من حواف إزالة.

وتحرير: توسيع هذا الوصف بعض الشيء

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

والآن تكرار عبر المسارات. إزالة أي مسار الذي يحتوي على حافة إزالة (ق) وإنقاص العداد لهذه العقدة. إذا تم decremented عداد العقدة إلى الصفر، كانت مضاءة والآن ليست كذلك.

Answer 5

وأود أن الحفاظ على المعلومات من العقد مصدر متصلة على حواف حين بناء الرسم البياني. (مثل إذا حافة ديها الاتصال إلى S1 مصادر وS2، تحتوي قائمة مصدره S1 و S2) وخلق العقد مع علم حواف المدخلات والمخرجات الحواف. عند إزالة الحافة، وتحديث حواف إخراج العقدة الهدف من تلك الميزة من خلال النظر في حواف مدخلات العقدة. وتعبر من خلال كافة العقد الهدف من حواف تحديثها باستخدام DFS أو BFS. (في حالة وجود رسم بياني دورة، والنظر في وضع العلامات). أثناء تحديث الرسم البياني، فمن الممكن أيضا للعثور على العقد دون أي الحافة التي لها علاقة المصدر (lit-> العقد مظلمة). ومع ذلك، فإنه قد لا يكون حلا جيدا، إذا كنت ترغب في إزالة الحواف متعددة في نفس الوقت منذ ذلك قد يؤدي إلى اجتياز مقارنة بنفس حواف مرارا وتكرارا.