मैं एक ग्राफ के लिए प्रभुत्व वृक्ष की गणना करने के लिए पथ संपीड़न के साथ लेंगौयर और तारजन एल्गोरिदम का उपयोग कर रहा हूं जहां लाखों नोड्स हैं। एल्गोरिदम काफी जटिल है और मुझे यह मानना है कि मैंने इसे पूरी तरह से समझने के लिए समय नहीं लिया है, मैं बस इसका उपयोग कर रहा हूं। अब मुझे रूट नोड के प्रत्यक्ष बच्चों के प्रभुत्व के पेड़ों की गणना करने की आवश्यकता है और संभवत: इस ऑपरेशन को दोहराते हुए एक निश्चित गहराई तक ग्राफ को फिर से भरना होगा। अर्थात। जब मैं रूट नोड के बच्चे के लिए प्रभुत्व वृक्ष की गणना करता हूं, तो मैं नाटक करना चाहता हूं कि रूट नोड को ग्राफ़ से हटा दिया गया है।पुनरावर्तक पेड़ की गणना करने के लिए कुशल तरीका?
मेरा सवाल यह है कि क्या इसका कोई कुशल समाधान है जो रूट नोड के लिए प्रारंभिक प्रभुत्व वाले पेड़ में पहले से गणना की गई तत्काल प्रभुत्व जानकारी का उपयोग करता है? दूसरे शब्दों में मैं प्रत्येक बच्चे के लिए खरोंच से शुरू नहीं करना चाहता क्योंकि पूरी प्रक्रिया काफी समय ले रही है।
नैतिक रूप से ऐसा लगता है कि यह संभव है क्योंकि ग्राफ में बहुत सारे नोड्स गहरे नीचे होंगे, जिनके पास मूर्तियां उनके ऊपर थोड़ी सी तरफ हैं और ग्राफ के शीर्ष पर परिवर्तनों से अप्रभावित हैं।
बीटीडब्ल्यू बस एक तरफ: यह विचित्र है कि प्रभुत्व वाले पेड़ों का विषय संकलक लोगों द्वारा "स्वामित्व" है और क्लासिक ग्राफ सिद्धांत पर पुस्तकों में इसका कोई उल्लेख नहीं है। जिस एप्लिकेशन का मैं इसका उपयोग कर रहा हूं - मेरे FindRoots जावा हीप विश्लेषक - कंपाइलर सिद्धांत से संबंधित नहीं है।
स्पष्टीकरण: मैं यहां निर्देशित ग्राफ के बारे में बात कर रहा हूं। मैं जिस रूट "का उल्लेख करता हूं वह वास्तव में सबसे बड़ी पहुंच के साथ नोड है। मैंने "ग्राफ़" के साथ "पेड़" के संदर्भों को प्रतिस्थापित करने के ऊपर दिए गए पाठ को अद्यतन किया है। मैं उनके बारे में पेड़ के रूप में सोचता हूं क्योंकि आकार मुख्य रूप से पेड़ की तरह है। ग्राफ वास्तव में एक जावा ढेर में वस्तुओं का है और जैसा कि आप कल्पना कर सकते हैं उचित रूप से पदानुक्रमिक है। ओओएम रिसाव विश्लेषण करते समय मुझे प्रभुत्व का पेड़ उपयोगी लगता है क्योंकि आप इसमें क्या रुचि रखते हैं "यह वस्तु जीवित रखती है?" और जवाब अंततः इसके प्रभुत्व है। डोमिनेटर पेड़ आपको < अहम > पेड़ों की बजाय लकड़ी को देखने की अनुमति देते हैं। लेकिन कभी-कभी बहुत सारे जंक पेड़ के शीर्ष पर तैरते हैं, इसलिए आपके पास इसके नीचे हजारों बच्चे सीधे रूट होते हैं। ऐसे मामलों के लिए मैं रूट के प्रत्येक प्रत्यक्ष बच्चों (मूल ग्राफ में) पर निहित प्रभुत्व वाले पेड़ों की गणना करने के साथ प्रयोग करना चाहता हूं और फिर अगले स्तर पर जा सकता हूं और इसी तरह। (मैं समय के लिए बैक लिंक की संभावना के बारे में चिंता करने की कोशिश नहीं कर रहा हूं :)
हां, यह मदद कर सकता है, धन्यवाद। मैं एल्गोरिदम के दूसरे भाग के बारे में चिंता करता हूं, हालांकि आमतौर पर समय के समान क्रम को डीएफएस के रूप में लेता है लेकिन कभी-कभी खराब होता है (और यही कारण है कि आपको निश्चित रूप से पथ संपीड़न की आवश्यकता है)। –