المجموعات المنفصلة

8. المجموعات المنفصلة

يقدّم هذا الفصل بنية بيانات أمرية (imperative) تحلّ مسألة تقسيم مجموعة منتهية إلى مجموعات فرعية منفصلة (disjoint subsets)، تُسمّى «أصنافاً» (classes). نريد أن نحدّد ما إذا كان عنصران ينتميان إلى الصنف نفسه، وأن ندمج صنفين في صنف واحد. وهاتان العمليتان هما ما يمنح البنية اسمها: union-find (اتحاد-بحث).

8.1 الفكرة الأساسية

بلا فقدان للعمومية، يمكننا افتراض أن المجموعة المراد تقسيمها تتكوّن من الأعداد الصحيحة n وهي {0,1,…,n− 1}. يعطي البرنامج 71 (انظر الصفحة 618) توقيع بنية كهذه. تنشئ العملية create n تجزيئاً جديداً للمجموعة {0,1,…,n − 1} يكون فيه كل عنصر صنفاً بذاته. وتحدّد العملية find صنف عنصر ما بإرجاع أحد الأعداد الصحيحة كممثل مميّز له. وعلى وجه الخصوص، يمكننا تحديد ما إذا كان عنصران يقعان في الصنف نفسه بمقارنة النتيجة التي يعطيها find لكل منهما. وأخيراً، تدمج العملية union صنفين من التجزيء، فتعدّل بنية البيانات في مكانها.

تكمن الفكرة الأساسية في ربط عناصر الصنف الواحد بعضها ببعض. وفي كل صنف تشكّل هذه الروابط رسماً بيانياً تنتهي فيه جميع المسارات إلى الممثل، وهو العنصر الوحيد المرتبط بنفسه. يوضّح الشكل 8.1 حالة قُسّمت فيها المجموعة {0,1,…,7} إلى صنفين ممثلاهما 3 و4 على التوالي.

الشكل 8.1: تقسيم المجموعة {0,1,…,7} إلى مجموعتين.

من الممكن تمثيل بنية كهذه باستعمال عقد تُخصَّص كل واحدة منها على حدة (انظر التمرين 8.5). ومع ذلك، فمن الأبسط، وكثيراً ما يكون أكثر كفاءة، استعمال مصفوفة تربط كل عدد صحيح بعدد صحيح آخر من الصنف نفسه. وتؤدي هذه الروابط إلى ممثل الصنف، وهو المرتبط بنفسه في المصفوفة. وهكذا، يُمثَّل تجزيء الشكل 8.1 بالمصفوفة التالية:

تتبع العملية find الروابط ببساطة حتى العثور على الممثل. وتبدأ العملية union بالعثور على ممثلي العنصرين ثم تربطهما معاً. ونقترح تحسينين في سبيل الكفاءة. يتمثّل الأول في إجراء ضغط المسار (path compression) أثناء البحث الذي تقوم به find: إذ تُربط جميع العناصر الموجودة على المسار المسلوك للوصول إلى الممثل به مباشرةً. ويتمثّل الثاني في تتبّع الرتبة (rank) لكل ممثل، أي الطول الأقصى لمسار في صنفه. وتُخزَّن هذه المعلومة في مصفوفة ثانية وتستعملها الدالة union لاختيار الممثل عند اتحاد الصنفين.

8.2 التنفيذ

نصف الآن شيفرة بنية union-find. النوع t سجلّ (record) يحتوي مصفوفتين: rank، وتحتوي رتبة كل صنف؛ وlink، وتحتوي الروابط بين العناصر.

  type t = {
    rank: int array;
    link: int array;
  }

المعلومة الموجودة في rank لا معنى لها إلا بالنسبة للعناصر i التي هي ممثلون، أي التي يكون فيها link.(i) = i. في البداية، يشكّل كل عنصر صنفاً بذاته (أي أنه ممثل نفسه)، ورتبة كل صنف تساوي 0.

  let create n =
    { rank = Array.make n 0;
      link = Array.init n (fun i -> i) }

تحسب الدالة find ممثل عنصر i. وتُكتب بشكل طبيعي كدالة تعاودية. نبدأ بحساب العنصر p المرتبط بـ i في المصفوفة t.link. فإن كان i نفسه، فإن i هو ممثل الصنف، ويكون هذا كافياً.

  let rec find t i =
    let p = t.link.(i) in
    if p = i then
      i

وإلا، نحسب بشكل تعاودي ممثل r للعنصر p بواسطة find t p. غير أنه قبل إرجاع r، نُجري ضغط المسار، أي نربط i بـ r مباشرة.

    else begin
      let r = find t p in
      t.link.(i) <- r;
      r
    end

وبهذه الطريقة، في المرة التالية التي نستدعي فيها find على i، سنجد r فوراً.

تبدأ العملية union بدمج صنفي عنصرين، i وj. نبدأ بحساب ممثليهما، ri وrj على التوالي. فإن كانا متساويين، فليس ثمة ما يستدعي المزيد.

  let union t i j =
    let ri = find t i in
    let rj = find t j in
    if ri <> rj then begin

وإلا، نقارن رتبتي الصنفين. فإن كانت رتبة ri أصغر تماماً من رتبة rj، جعلنا rj ممثلاً للاتحاد.

      if t.rank.(ri) < t.rank.(rj) then
        t.link.(ri) <- rj

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

      else begin
        t.link.(rj) <- ri;

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

        if t.rank.(ri) = t.rank.(rj) then
          t.rank.(ri) <- t.rank.(ri) + 1
      end
    end

من المهم أن الدالة union تستعمل الدالة find، وبالتالي تُجري ضغط المسار حتى في حالة انتماء i وj إلى الصنف نفسه. وتُعطى الشيفرة الكاملة لبنية union-find في البرنامج 72 (انظر الصفحة 621).

التعقيد

يمكننا أن نبيّن أنه، بفضل ضغط المسار والرتبة المرتبطة بكل صنف، فإن متتالية من m عملية من عمليات find وunion، تُنفَّذ على بنية تحتوي n عنصراً، تُنجَز في زمن كلي قدره O(mα(n,m))، حيث α دالة تنمو ببطء شديد للغاية. بل إنها تنمو ببطء إلى حدّ يمكننا أن نعتبرها معه ثابتة في كل الأغراض العملية، نظراً للقيود التي تفرضها الذاكرة والوقت على قيمتي n وm. ويمكننا من ثمّ افتراض أن كل عملية تستغرق زمناً ثابتاً مطفأً (amortized constant time). هذا التحليل معقّد ويقع خارج نطاق هذا الكتاب. ويمكن العثور على شرح مفصّل في Introduction to Algorithms [7، الفصل 22].

  type t
  val create: unit -> t
  val add: t -> int
  val find: t -> int -> int
  val union: t -> int -> int -> unit

  val num_classes: t -> int

  val iter_classes: (int -> unit) -> t -> unit

  type elt = { mutable rank: int; mutable link: elt }

  type ’a elt =
    { mutable rank: int; mutable link: ’a elt; data: ’a }

  type ’a elt
  val create_node: ’a -> ’a elt
  val find: ’a elt -> ’a elt
  val union: ’a elt -> ’a elt -> unit

  type t
  val create: int -> t
  val find: t -> int -> int
  val union: t -> int -> int -> t

  type t = { rank: int A.t; mutable link: int A.t }