تخزين معلومات المسار في خوارزمية Kruskal

Question

لقد أنشأت الحد الأدنى من الشجرة الممتدة باستخدام خوارزمية كروسكال وأردت معرفة كيفية تخزين المسارات

هذا هو الحد الأدنى للشجرة الممتدة Genacodicetagpre

Answer 1

يعتمد ذلك على مقدار المساحة الإضافية المتوفرة لديك. افترض أنك بحاجة إلى أن تكون موفرًا للمساحة:

1. وجِّه الحواف بطريقة يكون بها الهيكل الناتج معظم العقدة الأصلية لكل عقدة. كيف افعلها؟ ما عليك سوى اختيار عقدة وجعلها الجذر. الأطفال هم عقد المستوى الأول وما إلى ذلك
2. الآن قم بتخزين الرسم البياني الناتج بالتنسيق child-> الأصل (في الجدول الخاص بك ، يمكنك جعل العمود Loc1 فرعًا والعمود Loc2 الأصل. قم بفهرسته حسب الطفل)
3. بالنسبة إلى عقدتين معينتين ، a و y ، اللتان يجب حساب المسافة بينهما ، ابحث عن المجموعات الأبوية الخاصة بهما وانظر أين تتقاطع. السابق. إذا كان أصل x هو A ، فإن والد A هو B ... المسار الأبوي هو ABCDLMN (حيث N هو الجذر). وبالمثل ، إذا كان الجذر الأبوي لـ y هو EFLMN. كما ترى ، فإن أدنى جذر مشترك لكليهما هو L. المسافة من x-> L تساوي 5 ، y-> L تساوي 3 ،=> المسافة بين x و y هي 5 + 3= 8.

التعقيد: O (hlogn) حيث h هو ارتفاع الشجرة و n هو عدد العناصر في الشجرة (أفترض وقت البحث لكل عقدة في تسجيل الدخول).