إزالة تبعيات الدورة على رسم بياني موجه مع حواف ثابتة

Question

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

ما هي أفضل طريقة لإزالة الدورات في هذا الرسم البياني؟ يجب أن يكون اجتياز أكبر قدر ممكن من DFS ويبدأ في عقدة معينة.

Answer 1

لقد استخدمت الخوارزمية التالية لحل مشكلتي:

ابدأ برسم بياني لجميع الحواف الثابتة التي تم وضع علامة عليها تم تأكيد

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

بعد الخطوة المذكورة أعلاه ، أستخدم خوارزمية Tarjan لإيجاد المكونات المتصلة بقوة في الرسم البياني (يمكن القيام بذلك في وقت O (v + e)). سيكون عدد المكونات المتصلة بقوة صغيرة جدًا في حالاتي ، لذا فأنا فقط أذهب إلى كل مكون متصل بقوة وإزالة حافة واحدة قابلة للإزالة لكل منها. ثم أقوم بهذه الخطوة مرة أخرى حتى تبقى دورات أخرى في الرسم البياني.

هذا يعمل بشكل جيد وسريع بما فيه الكفاية.

Answer 2

ما يمكنك فعله هو استخدام خوارزمية Dijkstra: ابدأ برسم بياني يحتوي فقط على الحواف الثابتة. ثم قم بتطبيق تكييف الخوارزمية التي تبدأ بالرسم البياني الذي لديك بالفعل:

1. ابدأ بعقدة البداية ، وجميع الحواف الثابتة في مكون العقدة البدء. افترض أن هذه شجرة.
2. أضف العقدة الأقرب إلى الشجرة.
3. أضف أيضًا أي حواف ثابتة في مكون العقدة الذي أضفته للتو.
4. إذا كانت جميع العقد في الشجرة ، تنتهي. خلاف ذلك ، انتقل إلى الخطوة 4.

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

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

Answer 3

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

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

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

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]