हैश और वृत्तीय संदर्भ

Question

के साथ वस्तुओं की समानता के लिए जाँच करने के लिए कैसे मैं एक चक्रीय ग्राफ जैसी संरचना है कि नोड वस्तुओं का प्रतिनिधित्व करती है की है। ए नोड या तो स्केलर मान (पत्ता) या n> = 1 नोड (आंतरिक नोड) की एक सूची है।

संभावित परिपत्र संदर्भों के कारण, मैं बस एक रिकर्सिव हैशकोड() फ़ंक्शन का उपयोग नहीं कर सकता, जो सभी बच्चे नोड्स के हैशकोड() को जोड़ता है: यह एक अनंत रिकर्सन में समाप्त हो जाएगा।

जबकि हैशकोड() भाग कम से कम देखे गए नोड्स को ध्वजांकित और अनदेखा करके कम से कम करने योग्य लगता है, मुझे बराबर() के लिए एक काम करने वाले और कुशल एल्गोरिदम के बारे में सोचने में कुछ परेशानी हो रही है।

मेरे आश्चर्य के लिए मुझे इसके बारे में कोई उपयोगी जानकारी नहीं मिली, लेकिन मुझे यकीन है कि कई स्मार्ट लोगों ने इन समस्याओं को हल करने के अच्छे तरीकों के बारे में सोचा है ... सही?

उदाहरण (अजगर): क्योंकि यह बिल्कुल वैसा ही ग्राफ का प्रतिनिधित्व करता है

A = [ 1, 2, None ]; A[2] = A 
B = [ 1, 2, None ]; B[2] = B 

ए, बी के बराबर है।

बीटीडब्ल्यू। यह प्रश्न किसी भी विशिष्ट भाषा को लक्षित नहीं है, लेकिन जावा में वर्णित नोड ऑब्जेक्ट के लिए हैशकोड() और बराबर() को कार्यान्वित करना एक अच्छा व्यावहारिक उदाहरण होगा।

Answer 1

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

कार्यान्वयन बहुत ही कठोर हो सकता है। इसके बारे में here पढ़ें।

Answer 2

आपको ग्राफ चलने की आवश्यकता है।

यहां एक प्रश्न है: क्या ये ग्राफ बराबर हैं?

A = [1,2,None]; A[2] = A 
B = [1,2,[1,2,None]]; B[2][2] = B 

यदि ऐसा है, तो आपको (नोड, नोड) टुपल्स का एक सेट चाहिए। लूप को पकड़ने के लिए इस सेट का उपयोग करें, और जब आप लूप पकड़ते हैं तो 'सत्य' वापस करें।

यदि नहीं, तो आप थोड़ा अधिक कुशल हो सकते हैं, और नोड से नोड तक मानचित्र का उपयोग कर सकते हैं। फिर, ग्राफ़ चलते समय, पत्राचार का एक सेट बनाएं। (उपरोक्त मामले में, ए बी के अनुरूप होगा, ए [2] बी [2], & सी के अनुरूप होगा।) फिर जब आप नोड जोड़ी पर जाते हैं तो आप सुनिश्चित करते हैं कि सटीक जोड़ी मानचित्र में है; यदि यह ग्राफ नहीं है तो मेल नहीं खाता है।

Answer 3

मैं भी एक अच्छा जवाब जानना चाहता हूं। अब तक मैं विज़िट किए गए सेट के आधार पर समाधान का उपयोग करता हूं।

हैश की गणना करते समय, मैं ग्राफ़ संरचना को पार करता हूं और मैं विज़िट किए गए नोड्स का एक सेट रखता हूं। मैं दो बार एक ही नोड में प्रवेश नहीं करता हूं। जब मैंने पहले से देखे गए नोड को मारा, तो हैश बिना रिकर्सन के नंबर लौटाता है।

यह समानता तुलना के लिए भी काम करता है। मैं नोड डेटा की तुलना करता हूं और बच्चों पर बार-बार आह्वान करता हूं। जब मैंने पहले से देखे गए नोड को मारा, तो तुलना बिना रिकर्सन के सच हो जाती है।