أولاً ، دعونا نلقي نظرة على صورتين لضغط المسار:
مجموعات العدوانية النقابية هي بنية بيانات حساسة وعملية للغاية ، والتي تستخدم بشكل أساسي للتعامل مع مشكلة دمج بعض المجموعات غير المتقدمة. تشمل بعض الاستخدامات الشائعة توصيل الخسائر الفرعية ، وخوارزميات Kruskal لإيجاد الحد الأدنى لشجرة الامتداد ، والأسلاف الأقل شيوعًا (LCA).
عند استخدام مجموعة وإلقاء نظرة عليها ، سيكون هناك أولاً مجموعة من مجموعات Disjoint Dynamic S = {s 1 ، s 2 ، ⋯ ، s k} ، والتي تستخدم عمومًا عددًا صحيحًا لتمثيل عنصر في المجموعة.
قد تحتوي كل مجموعة على عنصر أو أكثر ، ويتم تحديد عنصر في المجموعة كممثل. ليس من المهم الاهتمام بالعناصر الواردة في كل مجموعة ، وليس من المهم الاهتمام بالعنصر الذي يتم اختياره كممثل. ما نهتم به هو أنه بالنسبة لعنصر معين ، يمكننا العثور بسرعة على المجموعة (التمثيل) حيث يوجد هذا العنصر ، ودمج المجموعات التي يوجد فيها العنصران ، والتعقيد الزمني لهذه العمليات ثابت.
هناك ثلاث عمليات أساسية للتحقق والجمع:
Makeet (s): قم بإنشاء مجموعة جديدة وبحث ، والتي تحتوي على مجموعات العناصر الفردية S.
Unionset (x ، y): يدمج المجموعات التي توجد فيها العنصر x والعنصر y ، وتتطلب أن تكون المجموعات التي توجد فيها x و y لا تتقاطع ، وإذا تتقاطعوا ، فإنها لا تندمج.
العثور على (x): ابحث عن ممثل المجموعة حيث يوجد العنصر x. يمكن أيضًا استخدام هذه العملية لتحديد ما إذا كان هناك عنصرين في نفس المجموعة. فقط قارن ممثليهم.
package com.datubulature.union_find ؛ // لدينا ، فإن الطبعة الخامسة من فئة الاتحاد ، UnionFind5 {// rance [i] يمثل عدد طبقات الشجرة التي تمثلها مجموعة من الرسم ، قد لا تكون قيمة الطبقة التي لا تدعو إلى أي شيء ، حيث لا تدعو إلى ذلك ، أي أيضًا ، لا نحافظ العمق. إنه مجرد معيار للمقارنة بين int [] رتبة [] ؛ Private Int [] الوالدين ؛ // Parent [i] يمثل العقدة الأصل التي أشار إليها عدد I-th element private int ؛ // عدد البيانات // constructor public UnionFind5 (int count) {rank = new int [count] ؛ Parent = new int [count] ؛ this.count = count ؛ // التهيئة ، يشير كل من الوالدين [i] إلى نفسه ، مما يشير إلى أن كل عنصر يشكل مجموعة خاصة به (int i = 0 ؛ i <count ؛ i ++) {parent [i] = i ؛ رتبة [i] = 1 ؛ }} // عملية البحث ، ابحث عن الرقم المحدد المقابل لعنصر p // o (h) التعقيد ، h هو ارتفاع شجرة int int (int p) {assert (p> = 0 && p <count) ؛ // ضغط المسار 1 بينما (p! = parent [p]) {parent [p] = parent [parent [p]] ؛ P = الوالدين [p] ؛ } إرجاع P ؛ // ضغط المسار 2 ، الخوارزمية العودية // if (p! = parent [p]) // parent [p] = find (parent [p]) ؛ // return parent [p] ؛ } // تحقق مما إذا كان العنصر P و Element Q ينتميان إلى مجموعة // o (h) ، H هو ارتفاع الشجرة المنطقية العامة (int p ، int q) {return find (p) == find (q) ؛ } // دمج المجموعة التي ينتمي إليها العنصر P و Element Q // O (H) التعقيد ، H هو ارتفاع الاتحادات الفراغية الشجرة العامة (int p ، int q) {int proot = find (p) ؛ int qroot = find (q) ؛ إذا (proot == QROOT) العودة ؛ . } آخر إذا (رتبة [qroot] <رتبة [proot]) {parent [qroot] = proot ؛ } آخر {// rany [proot] == rane [qroot] parent [proot] = qroot ؛ رتبة [QROOT] += 1 ؛ // في هذا الوقت ، أحافظ على قيمة الرتبة}}}لخص
ما ورد أعلاه هو كل التفسير التفصيلي لرمز ضغط المسار في هذه المقالة حول تنفيذ البرمجة Java وجمعها. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!