خوارزمية التحقق إذا كان موجها الرسم البياني مرتبطة بقوة

Question

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

طريقة واحدة للقيام بذلك هي إدارة DFS و BFS على كل عقدة و ترى كل والبعض الآخر لا يزال يمكن الوصول إليها.

هل هناك طريقة أفضل للقيام بذلك ؟

Answer 1

Tarjan في مرتبطة بقوة مكونات خوارزمية (أو <وأ href = "HTTP: // سوف en.wikipedia.org/wiki/Gabow's_algorithm "يختلط =" noreferrer "> Gabow في الاختلاف) وبطبيعة الحال يكفي. إذا كان هناك عنصر واحد فقط متصل بقوة، ثم في الرسم البياني يتم إتصال بقوة.

وكلاهما الزمن الخطي.

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

لتحقق لمجرد ما إذا كان الرسم البياني كله هو SCC واحد، والشروع في DFS من أي عقدة واحدة، وعند الانتهاء، إذا كان أدنى عمق يمكن الوصول إليه هو 0، وزار كل عقدة، ثم الرسم البياني كله ترتبط بقوة.

Answer 2

النظر في الخوارزمية التالية.

---

1. تبدأ في قمة العشوائية v من الرسم البياني G, و تشغيل DFS(G, v).

   • إذا DFS(G, v) فشل في الوصول إلى كل قمة في الرسم البياني G, ثم هناك بعض vertex u, مثل أنه لا يوجد أي توجه مسار من v إلى u, وبالتالي G هو ليست مرتبطة بقوة.

   • إذا لم تصل إلى كل نقطة, ثم هناك توجه مسار من v إلى كل قمة في الرسم البياني G.

2. عكس اتجاه جميع حواف في توجيه الرسم البياني G.

3. مرة أخرى تشغيل DFS ابتداء من الساعة v.

   • إذا DFS فشل في الوصول إلى كل نقطة, ثم هناك بعض vertex u, هذه التي في الرسم البياني الأصلي لا يوجد توجيه مسار من u إلى v.

   • من ناحية أخرى, إذا لم تصل إلى كل نقطة في الرسم البياني الأصلي هناك توجه مسار من كل vertex u إلى v.

وهكذا ، إذا ز "يمر" كل DFSs ، فمن مرتبطة بقوة.وعلاوة على ذلك, منذ DFS يعمل في O(n + m) الوقت, هذه الخوارزمية يعمل في O(2(n + m)) = O(n + m) الوقت, لأنه يتطلب 2 DFS traversals.

Answer 3

لمعرفة ما اذا كان كل عقدة لديه على حد سواء مسارات من وإلى كل عقدة أخرى في رسم بياني معين:

1. DFS / BFS من كافة العقد:

خوارزمية Tarjan في يفترض كل عقدة لديها d[i] العمق. في البداية، والجذر لديه أصغر العمق. ونحن نفعل ما بعد ترتيب DFS التحديثات d[i] = min(d[j]) لأي j جارة i. في الواقع BFS أيضا يعمل بشكل جيد مع d[i] = min(d[j]) حكم الحد هنا.

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

إذا كان هناك مسار الشحن من u إلى v، ثم d[u] <= d[v]. في SCC، d[v] <= d[u] <= d[v]، وبالتالي، كل العقد في SCC سيكون لها نفس العمق. لمعرفة ما إذا كان الرسم البياني هو SCC، ونحن تحقق ما إذا كانت كافة العقد لديها نفس d[i].

2. اثنين DFS / BFS من عقدة واحدة:

وبل هو نسخة مبسطة من Kosaraju في خوارزمية . بدءا من جذورها، ونحن معرفة ما اذا كان يمكن التوصل إلى كل عقدة من DFS / BFS. ثم، عكس اتجاه كل طرف. نحن معرفة ما اذا كان يمكن التوصل إلى كل عقدة من نفس الجذر مرة أخرى. انظر C ++ كود .

Answer 4

ويمكنك حساب جميع أزواج أقصر مسار و معرفة ما إذا كان أي هو لانهائي .

Answer 5

تم ذكرها خوارزمية Tarjan و. ولكن عادة ما أجد خوارزمية Kosaraju في أسهل لمتابعة الرغم من أنه يحتاج إلى traversals الرسم البياني . IIRC، بل هو أيضا شرحا جيدا جدا في CLRS.

Answer 6

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

Answer 7

وطريقة واحدة للقيام بذلك سيكون لتوليد Laplacian مصفوفة للحصول على الرسم البياني، ثم حساب القيم الذاتية، وأخيرا حساب عدد من الأصفار. الرسم البياني بقوة اتصال في حال وجود واحد فقط الصفر القيمة الذاتية.

ملحوظة: انتبه إلى طريقة مختلفة قليلا لإنشاء مصفوفة Laplacian لمخطط موجه

Answer 8

ويمكنك استخدام خوارزمية بسيطة DFS Kosaraju استنادا ان يفعل اثنين traversals DFS الرسم البياني:

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

والخوارزمي: 1) تهيئة كل القمم كما لم يزر.

2) هل لاجتياز DFS الرسم البياني بدءا من قمة الرأس أي ضد التعسفي. إذا لم DFS اجتياز زيارة كل القمم، ثم عودة كاذبة.

و3) عكس كل أقواس (أو العثور على تبديل أو عكس الرسم البياني)

و4) أجعل كل القمم كما زار ليس في الرسم البياني عكسه.

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

والوقت التعقيد: تعقيد وقت التنفيذ المذكور أعلاه هو نفس العمق البحث الأول الذي هو O (V + E) إذا تم تمثيل الرسم البياني باستخدام تمثيل قائمة الجوار