ما هي الطريقة الأكثر كفاءة لتحديد ما إذا كان الرسم البياني الموجه متصلًا بشكل منفرد؟

Question

أنا أعمل على مهمة حيث تطلب إحدى المشكلات استخلاص خوارزمية للتحقق مما إذا كان الرسم البياني الموجه G = (V ، E) متصلًا بشكل منفرد (يوجد في معظم المسار البسيط من U إلى V لجميع القمم المميزة u ، الخامس

بالطبع يمكنك أن تتحقق من القوة الغاشمة ، وهو ما أفعله الآن ، لكنني أريد أن أعرف ما إذا كانت هناك طريقة أكثر كفاءة. يمكن لأي شخص لي نقطة في الاتجاه الصحيح؟

Answer 1

هل جربت DFS.

Run DFS for every vertex in the graph as source
    If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.

التعقيد O (V^2) ، O (V) DFS على أنه لا يوجد تكرار.

Answer 2

هناك إجابة أفضل لهذا السؤال. يمكنك القيام بذلك في O (| V |^2). ومع مزيد من الجهد يمكنك القيام بذلك في الوقت الخطي.

أولاً ، تجد مكونات متصلة بقوة من G. في كل مكون قوي ، يمكنك البحث للعثور على هذه الحالات: 1) إذا كانت هناك حافة الأمام في هذا المكون ، فهي ليست متصلة بشكل منفرد ، 2) إذا كانت هناك حافة متقاطعة في هذا المكون ، ليس متصلاً منفردًا ، 3) إذا كان هناك حوافان خلفية على الأقل في شجرة متجذرة في Vertex U ، إلى أسلافك المناسبين ، فهذا ليس متصلاً بشكل منفرد.

يمكن القيام بذلك في O (E). (أعتقد باستثناء الحالة 3. لم أستطع تنفيذه جيدًا !!).

إذا لم تحدث أي من الحالات أعلاه ، فيجب عليك التحقق مما إذا كانت هناك حافة متقاطعة أو حافة أمامية على G^SCC (الرسم البياني G ، مع استبدال مكونات قوية بعقد واحدة) ، نظرًا لأننا لا نملك احتياطات ، يمكن القيام بذلك تكرار DFS على كل رأس من هذا الرسم البياني في O (| v |^2).

Answer 3

اقرأ هذا. انها تفسر حقا جيدا.

Answer 4

لا أوافق على أن تعقيدها سيكون O (V^2) ، كما في DFS ، لا نسميها لكل قمة كما نرى في مقدمة كتاب الخوارزمية أيضًا ، بناء الجملة DFS (G). نحن فقط ندعو DFS للحصول على رسم بياني كامل وليس لأي قمة واحدة على عكس BFS. لذلك هنا في هذه الحالة وفقًا لي ، يتعين علينا التحقق من ذلك عن طريق استدعاء DFS مرة واحدة. إذا تمت مواجهة قمة الزراعة مرة أخرى ، فإن الرسم البياني ليس متصلاً بشكل منفرد (بالتأكيد يتعين علينا الاتصال به لكل مكون غير متصل ولكنه مدرج بالفعل في الرمز ). لذلك سيكون التعقيد O (V+E). كما هو الحال هنا e = v لذلك يجب أن يكون التعقيد o (v).

Answer 5

فكرت في هذا: 1) قم بتشغيل DFS من أي قمة ، إذا كانت جميع القمم مغطاة في DFS بدون حواف أمامية (لا يمكن أن يكون هناك أي تقاطع لأن كل القمم لن تتم تغطية جميعها) ، فيمكن أن تكون مرشحًا محتملاً.

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

هذا يفعل في الوقت الخطي إذا كان هذا صحيحا.

Answer 6

ألق نظرة على تعريف المسار البسيط. يمكن أن يكون الرسم البياني الدوري متصلًا بشكل منفرد. DFS لن تعمل من أجل A->B, B->A, ، وهو متصل منفردة.

تستخدم الورقة التالية مكونًا متصلاً بقوة لحل هذا.

https://www.cs.umd.edu/~samir/grant/khuller99.ps

Answer 7

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

التعقيد: يا (ve)