الاتحاد والعثور: حافة جديدة لا تعني دمج مجموعتين

الخلاصة السريعة

في مثالنا نضيف A–B ثم D–E ثم B–C ثم A–C ثم C–D. أعداد المجموعات، مع الحالة الأولى، هي 6 و 5 و 4 و 3 و 3 و 2. عند إضافة A–C كان الطرفان متصلين عبر B، فلم يقل العدد. أما C–D فتصل المجموعة A,B,C بالمجموعة D,E؛ يبقى F وحده.

• بنية الاتحاد والعثور، أو Union–Find، تدير مجموعات منفصلة. تدمج مجموعتي عنصرين، وتعيد ممثل مجموعة العنصر؛ تساوي الممثلين يعني الانتماء إلى المجموعة نفسها. الممثل عنصر منها، وقد يتغير بعد الدمج. [1]
• رؤوس المثال A و B و C و D و E و F ثابتة. نبدأ دون حواف، ثم نضيف A–B و D–E و B–C و A–C و C–D بهذا الترتيب. الحواف غير موجهة؛ نتتبع الاتصال فقط، ولا نحسب أطوالًا أو أوزانًا.
• الأعداد 6 و 5 و 4 و 3 و 3 و 2 تتبع الدمج الفعلي. الحافة A–C لا تدمج مجموعتين، لأن A و C كانا في المجموعة A,B,C عبر A–B–C؛ ومع ذلك تضيف حافة حقيقية إلى الرسم.
• بعد C–D تصبح المجموعة الأولى A,B,C,D,E، والثانية F. أربع عمليات دمج فعلية من ست مجموعات تعطي 6 − 4 = 2؛ طرح الحواف الخمس يعطي 1 وهو عدد خاطئ هنا.
• بعد الإضافات يتصل A و D عبر A–C–D، رغم غياب الحافة A–D. اسم الممثل لا يصف حافة مباشرة أو مسارًا؛ في توثيق مثالنا نختار أصغر حرف في كل مجموعة لتسمية الصفوف فقط.
• نستخدم هنا نموذج إضافة الحواف مع حفظ قائمة الرسم منفصلة. حذف C–D يعيد ثلاث مجموعات، بينما حذف A–C وحدها يبقي مجموعتين. سجل الدمج السابق لا يتراجع تلقائيًا عند الحذف؛ أعد فحص الرسم المعدل، ولا تنقل هذه القاعدة إلى أسهم موجهة.

ما الذي تسجله المجموعة، وما الذي تسجله الحافة؟

الاتحاد والعثور بنية بيانات تجمع عناصر في مجموعات لا تتداخل. العثور يعيد ممثلًا من مجموعة العنصر، ومقارنة ممثلي عنصرين تحدد هل هما في المجموعة نفسها. إذا كان الممثلان متساويين، فلا يحتاج الاتحاد إلى دمج مجموعتين مختلفتين. [1]

نثبت الرؤوس A و B و C و D و E و F منذ البداية. ليس بينها أي حافة أولًا، لذا نعرض ست مجموعات منفردة. نضيف حافة واحدة في كل خطوة، دون حذف أو إضافة رؤوس أثناء الجدول.

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

سنكتب أعضاء المجموعة مفصولين بفواصل، مثل A,B,C. هذه القائمة لا تقول إن لكل زوج فيها حافة مباشرة، ولا تصف ترتيب طريق. أما A–B فتعني حافة أو خطوة بين رأسين، بحسب السياق المعلن. نحتفظ بقائمة الحواف إلى جانب قوائم الأعضاء كي لا نخلطهما.

أضف خمس حواف، وعد أربع عمليات دمج

أولًا نضيف A–B، فتجتمع A و B وتبقى C و D و E و F منفردة؛ العدد 5. ثانيًا نضيف D–E، فتظهر المجموعات A,B و C و D,E و F؛ العدد 4.

ثالثًا نضيف B–C. يقع B في A,B بينما C وحده، فتندمج المجموعتان في A,B,C. مع D,E و F يصبح العدد 3. يمكن الآن الانتقال بين A و C بالطريق A–B–C، حتى قبل إضافة الحافة المباشرة بينهما.

رابعًا نضيف A–C. الطرفان في A,B,C بالفعل، لذلك تبقى المجموعات A,B,C و D,E و F، والعدد 3. لكن الرسم تغير: أضيفت الحافة A–C، وصار له طريق مباشر بين A و C إلى جانب الطريق عبر B. لا نساوي بقاء التقسيم ببقاء كل حواف الرسم.

خامسًا نضيف C–D. ينتمي C إلى A,B,C، وينتمي D إلى D,E، فتندمج المجموعتان في A,B,C,D,E. الرأس F لم يتلق أي حافة، فيبقى منفردًا؛ العدد 2. يبين الجدول حالة كل إضافة، وتعرض الصورة الرئيسية الحالة بعد الخطوة الرابعة، قبل C–D.

لماذا لا نطرح عدد الحواف من عدد الرؤوس؟

بدأنا بست مجموعات، وكل دمج لمجموعتين مختلفتين يستبدلهما بمجموعة واحدة. لذلك يقل العدد بواحد في تلك الخطوة. في A–B و D–E و B–C و C–D حدث الدمج، أما A–C فلم يحدث؛ المجموع أربع عمليات دمج فعلية.

يكون الحساب 6 − 4 = 2. لو طرحنا الحواف الخمس كلها، لحصلنا على 6 − 5 = 1، خلافًا لوجود F منفردًا. الحافة الرابعة زادت قائمة الحواف من ثلاث إلى أربع، لكنها لم تقلل عدد مجموعات الاتصال.

بعد الخطوة الثالثة يصل الطريق A–B–C بين طرفي الحافة الرابعة قبل إضافتها. لهذا تستطيع أن تتحقق من عدم الدمج دون تخمين اللون: اكتب الطريق الموجود، ثم لاحظ أن أعضاء المجموعات لا يتغيرون عند إدخال A–C.

الصورة الداخلية تعرض الحالة بعد C–D. لون واحد يجمع A إلى E، ولون آخر يميز F. الحافة الجديدة C–D باللون الأخضر، دون سهم؛ هي الوصلة التي جمعت مجموعتي الصورة الأولى، ولا تمثل زمنًا أو تكلفة أو حجم مجموعة.

تساوي الممثلين لا يعني حافة مباشرة

الممثل تحدده البنية، وليس اسمًا ثابتًا مفروضًا لكل مجموعة؛ قد يتغير بعد الاتحاد. وهو عنصر داخل المجموعة، وتساوي ممثلي عنصرين يثبت انتماءهما إلى المجموعة نفسها. [1]

للتوثيق في هذا المثال فقط، نسمي كل مجموعة بأصغر حرف فيها. قبل C–D، اسم A,B,C هو A، واسم D,E هو D، واسم F هو F. بعدها نسمي A,B,C,D,E باسم A، وتبقى F باسم F. هذه قاعدة عرض اخترناها، وليست نتيجة لازمة لكل تنفيذ للاتحاد والعثور.

بعد الإضافات الخمس يكون A و D في مجموعة واحدة. يمكننا إظهار شاهد من قائمة الحواف: الطريق A–C–D يصل بينهما. لا توجد حافة A–D في قائمتنا، ولذلك لا نرسم خطًا مباشرًا بينهما اعتمادًا على اسم المجموعة.

يمكن تسمية المجموعة A,B,C,D,E باسم E بدل A في عرض آخر، دون تغيير الأعضاء أو الحواف. ما يهم لسؤال الاتصال هو أن يحصل عضوان من المجموعة نفسها على الممثل نفسه في الحالة الحالية؛ لا نفسر ترتيب الحروف كقرب أو أولوية.

الحذف يحتاج إلى مراجعة الرسم، والاتجاه يغير السؤال

نحفظ هنا قوائم أعضاء بعد عمليات دمج، ولا نعرض عملية تفصل مجموعة. إذا حذفنا حافة من الرسم، فلا يكفي شطب آخر سطر دمج كيفما اتفق. يجب فحص الحواف الباقية، لأن طريقًا بديلًا قد يحفظ الاتصال أو لا يحفظه.

في تعديل مستقل بعد الخطوة الخامسة، احذف C–D. تبقى الحواف A–B و D–E و B–C و A–C؛ لا وصلة بين A,B,C و D,E. تعود المجموعات الثلاث A,B,C و D,E و F. لا تصفها قائمة الدمج القديمة التي ما زالت تجمع A إلى E.

وفي تعديل آخر على الرسم النهائي، احذف A–C وحدها وأبق C–D. ما زال الطريق A–B–C–D–E يصل الرؤوس الخمسة، فيبقى العدد 2 مع F المنفرد. الاختلاف بين الحذفين يوضح لماذا نرجع إلى قائمة الحواف بدل طرح رقم من عدد المجموعات آليًا.

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