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