كيف تتحقق إذا كانت هناك دائرة في شجرة؟

Question

هذه شجرة:

1. سيكون هناك جذر واحد.

2. كل عقدة شجرة لديها صفر أو أكثر من أطفال.

3. يسمح أن تشير العقدان إلى نفس الطفل. قل ، كلتا العقدة A والعقدة B لديها طفل C.

ومع ذلك ، يحظر ذلك ،

العقدة A هي ذرية من العقدة B ، والعقدة B هي نسل العقدة A.

حالة واحدة محظورة

العقدة A لديها عقدة طفل C والعقدة د ،

كل من العقدة C و D لديها عقدة طفل E ،

العقدة E لديها طفل من A.

والسؤال هو ، كيف تحدد هذه الدائرة بأسرع طريقة؟

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

شكرا للتعليقات.

Answer 1

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

Answer 2

يمكن العثور على الدوائر باستخدام 2 مؤشرات وتعزيزها على فترات زمنية مختلفة. في نهاية المطاف ، ستتطابق المؤشرات ، مما يشير إلى حلقة ، أو أن تصل إلى "أسرع" ثم تنتهي. عادة ما يتم طرح السؤال على القوائم المرتبطة ، وليس الأشجار.