एक पेड़ में दो यादृच्छिक नोड्स के बीच दूरी निर्धारित करें

Question

एक सामान्य पेड़ को देखते हुए, मुझे दो नोड्स v और w के बीच की दूरी चाहिए।

विकिपीडिया states the following: w हो सकता है v से दूरी:

सबसे कम आम पूर्वजों की संगणना उपयोगी, उदाहरण के लिए, एक प्रक्रिया के तहत एक पेड़ में एक नोड के जोड़े के बीच की दूरी को निर्धारित करने के लिए किया जा सकता है जड़ से v तक की दूरी के रूप में गणना की जाती है, साथ ही रूट से दूरी तक की दूरी, रूट से दूरी से दो गुना कम से कम अपने सबसे सामान्य पूर्वजों तक की गणना की जाती है।

मान लीजिए कि d(x) जड़ जो हम 1 करने के लिए सेट से नोड x की दूरी को दर्शाता हैं। d(x,y) दो शीर्षऔर y के बीच की दूरी को दर्शाता है। lca(x,y) वर्टेक्स जोड़ी x और y के सबसे कम आम पूर्वजों को दर्शाता है।

इस प्रकार अगर हम 4 और 8, lca(4,8) = 2 इसलिए है, उपरोक्त विवरण, d(4,8) = d(4) + d(8) - 2 * d(lca(4,8)) = 2 + 3 - 2 * 1 = 3 के अनुसार। बढ़िया, यह काम किया!

हालांकि, मामले ऊपर कहा गया है शिखर जोड़ी (8,3) (lca(8,3) = 2) d(8,3) = d(8) + d(3) - 2 * d(2) = 3 + 1 - 2 * 1 = 2. हालांकि यह गलत है, दूरी d(8,3) = 4 के रूप में ग्राफ पर देखा जा सकता के लिए असफल रहा है। एल्गोरिदम परिभाषित रूट पर पार होने वाली किसी भी चीज के लिए असफल प्रतीत होता है।

मुझे क्या याद आ रही है?

Answer 1

आपने lca(8,3) = 1 को याद किया, और = 2 नहीं। इसलिए d(1) == 0 जो इसे बनाता है:

d(8,3) = d(8) + d(3) - 2 * d(1) = 3 + 1 - 2 * 0 = 4 

Answer 2

उचित 2 नोड, अर्थात् एक के बाद एक सही, d(lca(8,2)) == 0, नहीं 1 तुम्हारे पास है के रूप में अपने व्युत्पत्ति में लिए। रूट से दूरी - जो इस मामले में एलसीए है - स्वयं शून्य है। तो

d(8,2) = d(8) + d(2) - 2 * d(lca(8,2)) = 3 + 1 - 2 * 0 = 4 

सच है कि आप दो नोड्स 2 लेबल है कि शायद भ्रामक बातें है।

संपादित करें: ताकि एक नोड मूल रूप से लेबल 2 अब 3. लेबल किया गया है इस मामले में पोस्ट संपादित किया गया है, व्युत्पत्ति अब सही है, लेकिन बयान

the distance d(8,2) = 4 as can be seen on the graph 

गलत है, घ (8 , 2) = 2.