मैं बहु-स्तर संदर्भों और निर्भरताओं में परिपत्र तर्क या रिकर्सन का पता कैसे लगा सकता हूं

Question

मेरे पास बहु-स्तर निर्भरता का ग्राफ है, और मुझे इस ग्राफ में किसी भी परिपत्र संदर्भ का पता लगाने की आवश्यकता है।

एक = बी

B = C

सी = [डी, बी]

डी = [सी, एक]

किसी ने इस तरह एक समस्या है?

कोई समाधान ???

धन्यवाद और अंग्रेजी द्वारा खेद है।

========= अद्यतन ==========

मैं एक स्थिति थी।

2 = 1

3 = 2

4 = [2, 3]

5 = 4

इस मामले में, मेरी पुनरावर्ती कोड पुनरावृति दो "4" संदर्भ में बार, लेकिन यह संदर्भ अनंत लूप उत्पन्न नहीं करते हैं। मेरी समस्या यह जानना है कि जब फ़ंक्शन एक बार से अधिक बार संदर्भित करता है और अनंत लूप नहीं होता है और उपयोगकर्ता को सूचित करने के लिए अनंत लूप कब होता है।

1 = 4

2 = 1

3 = 2

4 = [2, 3]

5 = 4

इस मामले से थोड़ा भिन्न है 2 वां उदाहरण यह एक अनंत पाश उत्पन्न करता है। मुझे कैसे पता चलेगा कि मामले अनंत लूप उत्पन्न करते हैं या नहीं?

Answer 1

विशिष्ट रूप से पहचाने गए नोड्स की एक सूची रखें। पूरे पेड़ के माध्यम से लूप का प्रयास करें, लेकिन सूची में नोड्स को तब तक जांचते रहें जब तक कि आपको एक नोड को एक बच्चे के रूप में संदर्भित न किया जाए जो पहले से ही अद्वितीय सूची में है - इसे वहां से ले जाएं (लूप को संभालें या बस इसके आधार पर इसे अनदेखा करें आवश्यकता)

Answer 2

Topological sorting। विकिपीडिया पर विवरण स्पष्ट है और आपके सभी उदाहरणों के लिए काम करता है।

असल में आप ऐसे नोड से शुरू करते हैं जिसमें कोई निर्भरता नहीं है, इसे सॉर्ट किए गए नोड्स की सूची में रखें, और उसके बाद प्रत्येक नोड से उस निर्भरता को हटा दें। आपके लिए दूसरा उदाहरण जिसका अर्थ है कि आप 1 से शुरू करते हैं। एक बार जब आप 1 पर सभी निर्भरताओं को हटा देते हैं तो आप 2 के साथ छोड़ दिए जाते हैं। आप उन्हें 1,2,3,4,5 क्रमबद्ध करते हैं और देखते हैं कि कोई चक्र नहीं है।

आपके तीसरे उदाहरण के लिए, प्रत्येक नोड की निर्भरता होती है, इसलिए शुरू करने के लिए कहीं भी नहीं है। इस तरह के ग्राफ में कम से कम एक चक्र होना चाहिए।