إعجاب شجرة الامتداد وليس على حافة شجرة الامتداد، كيفية تشكيل لقاعدة دورة؟

Question

ولدي رسم بياني مع E الحافة وفيرتكس V، يمكنني العثور على شجرة تمتد باستخدام كروسكال خوارزمية (أو أي دولة أخرى اجتياز-التراجع-اجتياز مرة أخرى نوع من خوارزميات)، الآن أريد أن أجد جميع القواعد دورة التي يتم إنشاؤها بواسطة utilitizing أن تمتد شجرة والحواف التي ليست على الشجرة، أي خوارزمية أن يسمح لي للقيام بذلك، إلى جانب بحث شامل؟

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

Answer 1

وخوارزمية بسيطة نستخدمها لإيجاد دورات في الرسوم البيانية:

<اقتباس فقرة>   

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

وقد يكون من المفيد أن يكون هناك مؤشر (جدول هاش) من كل أسلاف عقدة حافة دوري بحيث سريعة للعثور على سلف مشترك.

وأشك في أن هذا هو أفضل خوارزمية لكنه سريع إلى حد ما.

تعديل في repsonse للتعليق كل عقدة في الشجرة الممتدة لديها أحد الوالدين. عندما يتم التوصل إلى عقدة في حافة دوري يحسب قائمتها للقائمة الأجداد (List<Node>This يمكن فهرستها للسرعة (أي يحتوي على () هو < O(n)). عندما تم العثور على حافة دورية مع عقدتين (n1, n2) ثم تكرار خلال أسلاف n1, n1.ancestorList ( بسرعة منذ تم بالفعل إنشاء قائمة)، واختبار ما إذا كان سلف في n2.ancestorList. إذا كان (commonAncestor) هو، ثم بالضبط تلك الأجداد اجتاز تتوافق مع دورات، ثم تكرار خلال N2 حتى تصل commonAncestor (السريع). يجب أن تتوقف الساعة على عدد من الحواف الدائرية، جنبا إلى جنب مع البحث في القوائم (وربما O(logN) لكن رخيصة). ليست هناك حاجة إلى إعادة استكشاف الرسم البياني وليس هناك التراجع.

Answer 2

وبعد بناء تمتد شجرة، أعاد على كل حافة (A، B) وهي ليست في شجرة والعثور على الأقل الجد المشترك (LCA) لعقد هذه الحافة، دورتك سيكون المسار من A -> LCA -> B -> A

ويمكنك استخدام هذا الرابط: http://www.topcoder.com/tc؟module=Static&d1 = دروس و D2 = lowestCommonAncestor     لكفاءة أدنى تنفيذ الجد خوارزمية المشترك.