التعقيد الزمني لخوارزمية فلوري

Question

هل يمكنك مساعدتي في معرفة التعقيد الزمني لخوارزمية فلوري (التي تستخدم للحصول على دائرة أويلريان)؟

Answer 1

هنا:http://roticv.rantx.com/book/eulerianpathandcircuit.pdf.يمكنك أن تقرأ من بين أشياء أخرى، أنها س (ه)، عدد الحافة الخطية.

Answer 2

خوارزمية فلوري ليست كاملة حقا حتى تحدد كيفية تحديد حواف الجسر. أعطى طرجان خوارزمية خطية محددة لتحديد جميع الجسور (انظر http://en.wikipedia.org/wiki/bridge_(graph_theory) ) لذا تنفيذ ساذج خوارزمية Reran Tarjan بعد كل حافة محذوف سيكون O (E ^ 2). ربما توجد طرق أفضل لتعيين مجموعة الجسور، ولكن هناك أيضا خوارزمية O (E) أفضل. (يرى http://www.algorithmist.com/index.php/euler_tour#fleury.27s_algorithm. ؛ ليس موقعي :))

Answer 3

تتضمن خوارزمية فلوري الخطوات التالية:

1. تأكد من أن الرسم البياني يحتوي على 0 أو 2 رؤوس فردية.

2. إذا كان هناك 0 قمم فردية، ابدأ من أي مكان.إذا كان هناك قمتين فرديتين، فابدأ من إحداهما.

3. اتبع الحواف واحدة تلو الأخرى.إذا كان لديك خيار بين الجسر وغير الجسر، فاختر دائمًا غير الجسر.

4. توقف عند نفاد الحواف.

إذا تم اكتشاف الجسور بواسطة خوارزمية تارجان وتم تخزين هذه الجسور في مصفوفة مجاورة، فلن نحتاج إلى تشغيل خوارزمية تارجان في كل مرة للتحقق مما إذا كانت الحافة عبارة عن جسر أم لا.يمكننا التحقق من ذلك في وقت O(1) لجميع استعلامات الجسر الأخرى.وبالتالي يمكن تقليل التعقيد الزمني لخوارزمية Flury إلى O(V+E) {لأن هذا هو DFS} ولكن هذه الطريقة تحتاج إلى مساحة إضافية O(V2) لتخزين الجسور.