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

{{{name}}}
النوع	{{{type}}}
تعقيد زمني in رمز O الكبير
	المتوسط	أسوء حالة
المساحة
بحث
ادراج
مسح

عملية إنشاء مجموعة (MakeSet) أنشأت 8 مجموعات منفصلة

بعد استخدام عملية الاتحاد (Union)، تم دمج بعض المجموعات معًا

في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة عمليتان مفيدتين هما:

1- الإيجاد (Find) : تحديد في أي الفروع يوجد العنصر، تعيد عملية الإيجاد بالعادة العنصر من هذه المجموعة عن طريق ممثله عبر مقارنة نتيجتي علميتي بحث، ليتم تحديد إذا كان العنصرين في نفس المجموعة ام لا.

2- الاتحاد (Union) : حيث يقوم بجمع فرعين في فرع واحد.

أما العملية المهمة الأخرى وهي صناعة المجموعة (MakeSet) والتي تصنع مجموعة تحتوي على عنصر واحد عديم الأهمية بالعادة. مع هذه العمليات الثلاث، يمكن حل العديد من مشاكل التقسيم العملية.)

لكي يتم تحديد هذه العمليات بوضوح، يجب ان يكون هناك طريقة لتمثيل هذه البيانات، أحد هذه المناهج المتداول عليها هي اختيار عنصر ثابت من كل مجموعة يسمى الممثل، ليمثل المجموعة بأكملها. إذًا Find(x) تعيد ممثل المجموعة التي ينتمي اليها x، وعملية الاتحاد Union تأخد ممثلي المجموعتين لدمجهما معا في مجموعة واحدة.

المجموعة المنفصلة ذات القوائم المترابطة

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

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 قام سلفيان كونكون وو جين كريستوف فليتر طور نسخة متكررة من هيكلة المجموعة المنفصلة بحيث يسمح للهيكل السابق بالحفاظ على كفائته بستخدام اثبات مساعد كوك