كشف الدورة بخوارزمية فلويد: تتبّع المؤشرين وحدد مدخل الحلقة

تستخدم طريقة فلويد مؤشرين: يتقدم البطيء خطوة والسريع خطوتين على المسار نفسه، ونبحث عن اجتماعهما بعد الحركة. تُعرف أيضًا بطريقة الأرنب والسلحفاة. [1]

سننشئ سبع عقد مسماة A إلى G. تتبع كل عقدة رابطًا واحدًا إلى التالية، ويعيد رابط G القراءة إلى D. نريد جوابًا يمكن التحقق منه: هل توجد حلقة من نقطة البداية؟ أين تبدأ؟ وكم عقدة نمر بها في لفة كاملة؟

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

• في مثالنا A→B→C→D→E→F→G→D، يلتقي المؤشران أول مرة عند E بعد أربع دورات تشغيل.
• إعادة أحد المؤشرين إلى A وتحريكهما معًا خطوة واحدة ينتهي بلقاء عند D بعد ثلاث خطوات.
• الدوران من D إلى D يمر بأربع روابط، لذلك طول الحلقة أربعة.
• تساوي القيم المخزنة داخل عقد مختلفة لا يكفي؛ نقارن هوية العقدة نفسها.
• اختبرنا 3800 حالة مقابل مرجع يحفظ أول زيارة، مع حالات منتهية وعقد تشير إلى نفسها وحلقات غير متاحة من البداية.

اجعل الرابط جزءًا من المدخل

اكتب الأسماء على ورقة وارسم سهمًا واحدًا خارج كل عقدة. سهم A يصل إلى B، ثم B إلى C، ثم C إلى D، وتتوالى الأسهم حتى G الذي يعود إلى D. عند بدء القراءة من A لن نجد نهاية فارغة؛ سنقرأ D وE وF وG مرارًا بعد المرور بالجزء الأول.

في البرنامج أعطينا كل عقدة هوية منفصلة وحقلًا باسم next. يمكن أن يحمل هذا الحقل عقدة أخرى أو None للدلالة على النهاية. نتعامل مع بنية محدودة وروابط لا تتغير أثناء الفحص. وجود أكثر من سهم اختياري عند عقدة يحتاج قرارًا آخر لا يمثله هذا المدخل.

نفذ الحركة قبل اختبار اللقاء

نضع المؤشرين عند A أولًا. تساويهما في هذه اللحظة سببه التهيئة، فلا نستنتج منه حلقة. نحرك البطيء مرة والسريع مرتين ثم نقارن. في الدورة الأولى يصل البطيء إلى B والسريع إلى C؛ وفي الثانية إلى C وE؛ وفي الثالثة إلى D وG؛ وفي الرابعة يجتمعان عند E.

عند الدورة الثالثة مر السريع بأكثر من عقدة بين المقارنتين: ينتقل من E إلى F ثم G. لا نعد مرور السريع بعقدة كان البطيء عندها في وقت سابق لقاءً؛ المقارنة تخص موضعيهما بعد دورة التحريك نفسها. لذلك حفظنا الجدول كاملًا بدل وصف الحركة بعبارة «يلحقه في النهاية» فقط.

افحص النهاية قبل الخطوة الثانية

تعبير الحركة يطبق الرابط مرة على البطيء ومرتين على السريع. يحافظ الكود التالي على مؤشرين؛ أضفنا شرط النهاية الفارغة ليلائم قائمتنا المنتهية أيضًا. [1]

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

إذا كان الرأس None، لا تدخل الحلقة وتعود النتيجة خطأ. وإذا كانت لدينا A→B→C→None، يصبح السريع عند C بعد الدورة الأولى؛ رابط C فارغ، فيتوقف الاختبار قبل محاولة قراءة حقل من فراغ. لا نقرأ fast.next.next قبل التأكد من وجود fast ورابطه الأول.

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

فرّق بين تكرار القيمة وتكرار العقدة

أنشأنا قائمة من ثلاث عقد مختلفة تحمل جميعها القيمة 7، وروابطها A→B→C→None. بعد أول حركة ستكون قيمة البطيء 7 وقيمة السريع 7، لكنهما في B وC. أعاد كاشف الهوية أن القائمة بلا حلقة. فاحص يعتمد مساواة القيم كان سيعطي إنذارًا زائفًا لهذا المدخل.

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

ارجع إلى المدخل ثم احسب طول اللفة

بعد اللقاء، نعيد مؤشرًا إلى الرأس ونترك الآخر عند موضع اللقاء، ثم نحركهما خطوة واحدة كل مرة. نقطة اجتماعهما التالية هي مدخل الحلقة. [2]

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

لحساب الطول ثبت علامة عند D وحرك مؤشرًا آخر حتى يعود إليها. سجلنا D→E خطوة أولى، ثم E→F ثانية، ثم F→G ثالثة، ثم G→D رابعة. لا نضيف D مرتين بوصفها عقدتين مختلفتين؛ القيمة أربعة تعد الروابط التي تعيدنا إلى الموضع نفسه.

هذه الأعداد تصف المثال من رأسه المختار. لو بدأنا الفحص من E، فلن نمر بالجزء A وB وC؛ يجب أن نحسب النتيجة من البداية الجديدة. وبالمثل أنشأنا بنية فيها A→B→None وعقدة منفصلة تشير إلى نفسها: الفحص من A لا يجد الحلقة المنفصلة، بينما الفحص من تلك العقدة يجدها.

قارن بمرجع يسجل أول زيارة

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

ولدنا جميع خرائط الرابط الواحد للأحجام من صفر إلى أربع عقد، مع السماح لكل رابط بعقدة أو None، وفحصنا كل رأس ممكن والرأس الفارغ؛ نتجت 3413 حالة بدء. وأضفنا 336 سلسلة ذات جزء أول من صفر إلى عشرين عقدة وحلقة من واحدة إلى ست عشرة، و51 قائمة منتهية أطوالها من صفر إلى خمسين.

في الحالات الـ3800 قارنا المدخل والطول وطول الجزء السابق، وقارنا نتيجة الكاشف المختصر، وتحققنا من بقاء الروابط كما كانت. مع اختبارات المثال والهوية والحلقة المنفصلة، بلغ مجموع التأكيدات 11404. نميز الكاشف عن أداة شرحه: حفظ جدول التتبع ومرجع الزيارات يستعمل ذاكرة إضافية، بينما دالة الكشف المعروضة تحتفظ بمرجعين فقط دون سجل للزيارات.

المصادر

1. MIT — Floyd’s cycle detection، القسم 10.7
2. Cornell — Linked Data، التمرين 13.11

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