الدورات في برامج الأنساب: كيف تعمل تحت الغطاء بلغة C++

مقدمة: لماذا لا توجد حلقات زمنية في شجرة العائلة

تخيل: أنت تكتب برنامجًا لبناء شجرة عائلة. كل شيء يسير على ما يرام حتى يضيف المستخدم رابطًا: "إيفان هو والد بيتر، بيتر هو والد إيفان". يتجمد البرنامج، ويذهب التكرار إلى ما لا نهاية، ويحصل المستخدم على Stack Overflow بالمعنى الحرفي للكلمة. موقف مألوف؟ هذا السؤال هو من أكثر الأسئلة شيوعًا على Stack Overflow (آلاف المشاهدات)، وليس من دون سبب.

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

\n

هام: المقالة مكتوبة للموقع التعليمي pythonlib.ru، لكن الكود كامل بلغة C++ - وهذا مثال ممتاز على كيفية عبور الخوارزميات لحدود اللغات.

\n

لماذا تعتبر الدورات مشكلة لبرامج الأنساب؟

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

\n
• أليس هي والدة بوب
\n
• بوب هو والد أليس
\n

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

\n
• تجميد البرنامج
\n
• تجاوز سعة المكدس (stack overflow)
\n
• استهلاك لا نهائي للذاكرة
\n

لذلك، اكتشاف الدورات في الرسم البياني هو مهمة أساسية لأي تطبيق أنساب جاد.

هيكل البيانات: كيفية تخزين شجرة العائلة بلغة C++

قبل الحديث عن الخوارزميات، يجب تحديد التمثيل. أقترح استخدام قائمة الجوار (adjacency list) - فهي فعالة وواضحة.

#include <iostream>\n#include <unordered_map>\n#include <vector>\n#include <string>\n#include <stack>\n\nclass FamilyTree {\nprivate:\n    // كل شخص هو عقدة باسم فريد (ID)\n    // الحواف: والد -> طفل\n    std::unordered_map<std::string, std::vector<std::string>> parentToChild;\n    \npublic:\n    void addRelation(const std::string& parent, const std::string& child) {\n        parentToChild[parent].push_back(child);\n        // إذا لم يكن الطفل موجودًا في الرسم البياني - أضف قائمة فارغة\n        if (parentToChild.find(child) == parentToChild.end()) {\n            parentToChild[child] = {};\n        }\n    }\n    \n    // ... طرق الاجتياز\n};\n

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

كيفية اكتشاف الدورة: خوارزمية البحث في العمق (DFS)

الطريقة القياسية للعثور على دورة في رسم بياني موجه هي البحث في العمق (DFS) المعدل. الفكرة بسيطة: نضع علامات على الرؤوس بثلاثة ألوان:

\n
• أبيض (0) - لم تتم زيارتها
\n
• رمادي (1) - قيد الاجتياز (في مكدس التكرار الحالي)
\n
• أسود (2) - تمت معالجتها بالكامل
\n

إذا واجهنا أثناء DFS رأسًا بلون رمادي - فهذه دورة. دعنا ننفذ هذا بلغة C++.

#include <unordered_map>\n#include <string>\n#include <vector>\n\nenum class Color { WHITE, GRAY, BLACK };\n\nclass CycleDetector {\nprivate:\n    std::unordered_map<std::string, std::vector<std::string>>& graph;\n    std::unordered_map<std::string, Color> color;\n    \n    bool