هيكلة بيانات المجموعات المنفصلة

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

MakeSet تقوم بصناعة قائمة تحتوي على عنصر واحد، أما Union تقوم بدمج قائمتين معًا بعملية ذات وقت ثابت إذا كان هناك مؤشر لذيل القائمة، أما العقبة في وجه هذا التطبيق هي عملية البحث Find فهي تتطلب O(n) أو زمن يزداد بشكل خطي ليمر عبر القائمة من الخلف إلى رأس القائمة.

لكن من الممكن تجاهل هذا بإضافة مؤشر يؤشر على رأس القائمة في كل عقدة (node) تابعة لهذه القائمة وبتالي ستأخذ عملية البحث وقت ثابت حيث يعود هذا المؤشر بشكل مباشر إلى الممثل لهذه القائمة لكن بهذه الحالة سنقع في مشكلة أخرى حيث سنصبح بحاجة إلى تعديل كل العقد ليؤشروا على رأس قائمة من القائمتين في حال استخدمنا عملية الاتحاد Union وهذا يتتطلب O(n) عملية.

عندما يكون طول القائمة معروف يمكن تقليل الوقت عبر إضافة القائمة الأصغر إلى القائمة الأكبر، باستخدام هذا الاتحاد الموزون سلسلة m من صنع المجموع وعمليتي الإيجاد والاتحاد على n من العناصر يتطلب O(m+nlogn) عملية. اما إذا اردنا أداء أفضل من هذا فعلينا التفكير بهيكلة بينات مختلفة عن القوائم المنفصلة.

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

في غابة المجموعة المنفصلة الممثل لكل مجموعة هو جذر شجرة المجموعة حيث تقوم عملية البحث بتتبع الأب لكل عقدة حتى تصل إلى جذر الشجرة وتقوم عملية الدمج بحيث يتم رفح جذر أحد الأشجار إلى الشجرة المراد الدمج اليها حيث يتم كتابة العمليات الثلاث بالشكل التالي:

function MakeSet(x)
 x.parent := x

function Find(x)
 if x.parent == x
  return x
 else
  return Find(x.parent)

function Union(x, y)
 xRoot := Find(x)
 yRoot := Find(y)
 xRoot.parent := yRoot

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

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

function MakeSet(x)
 x.parent := x
 x.rank := 0

function Union(x, y)
 xRoot := Find(x)
 yRoot := Find(y)
 if xRoot == yRoot
  return

 // x and y are not already in same set. Merge them.
 if xRoot.rank < yRoot.rank
  xRoot.parent := yRoot
 else if xRoot.rank > yRoot.rank
  yRoot.parent := xRoot
 else
  yRoot.parent := xRoot
  xRoot.rank := xRoot.rank + 1

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

function Find(x)
 if x.parent != x
  x.parent := Find(x.parent)
 return x.parent

هيكلة المجموعات المنفصلة للبيانات نموذج لتقسيم المجموعة على سبيل المثال يمكن استخدام هذه الهيكيلة لمعرفة إذا كان الرأسين تابعين لنفس العنصر أو إذا كان هناك دائرة مكتملة في الرسوم غير الموجهة، وتستخدم في مكتبة دفع الرسومات لتنفيذ وظائف المكونات المتصلة المتزايدة، كما تستخدم ايضًا في تطبيق خوارزمية كروسكال .

رغم أن الأفكار المستخدمة في المجموعات المنفصلة ومعروفة منذ زمن، كان روبرت ترجان أول من أثبت الحد الأعلى والنسخة المقيدة من الحد الأدنى بعكس وظيفة اركمان عام 1975، حتى هذا الوقت كان أفضل حد مكتشف عر هوبكرافت ويلمان حيث كان O(logn)، الخوارزمية المعادة ل n ، معادلة أخرى تنمو ببطء.

كما طور ترجان وفان لوين خوارزمية البحث تقوم باعادة النتيجة بمرور واحد أكثر دقة.

في عام 2007 قام سلفيان كونكون وو جين كريستوف فليتر طور نسخة متكررة من هيكلة المجموعة المنفصلة بحيث يسمح للهيكل السابق بالحفاظ على كفائته بستخدام اثبات مساعد كوك

• بوابة علم الحاسوب