बाइनरी पेड़ में दो सबसे दूर तत्वों को ढूंढना

Question

मैं एक एल्गोरिदम खोज रहा हूं जो कि बाइनरी पेड़ में दो सबसे दूर तत्वों को ढूंढ सकता है, केवल एल्गोरिदम के लिए, किसी भी विशेष भाषा की तलाश नहीं कर रहा है।

धन्यवाद।

Answer 1

इसे पेड़ व्यास कहा जाता है।

int diameter(Tree * t) // post: return diameter of t 
{ 
    if (t == 0) return 0; 
    int lheight = height(tree->left); 
    int rheight = height(tree->right); 
    int ldiameter = diameter(tree->left); 
    int rdiameter = diameter(tree->right); 
    return max(lheight + rheight + 1, max(ldiameter,rdiameter)); 
} 

alt text http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.jpg

copied code and images from here।

Answer 2

जो आप खोज रहे हैं उसे graph diameter नाम दिया जा सकता है। इसे प्राप्त करने के लिए आपको किसी भी कशेरुक से किसी अन्य को पथ की गणना करने की आवश्यकता होगी और फिर उन सभी के माध्यम से जाना होगा और सबसे बड़ा खोजना होगा।
Dijkstra's algorithm या distance matrix (जिसे adjacency matrix को सशक्त करके हासिल किया जा सकता है) का उपयोग करके हासिल किया जा सकता है, हालांकि इसमें डिजस्ट्रा के एल्गोरिदम से अधिक समय लगेगा।

Answer 3

चूंकि यह एक पेड़ है, वहां किसी भी जोड़ी के बीच केवल एक रास्ता है। यह ग्राफ के व्यास को ढूंढना हमारे लिए आसान बनाता है।

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

इस काम का सबूत अभ्यास के रूप में क्यों छोड़ा गया है इसका प्रमाण।

एक और तरीका भी है जो रूट के प्रत्येक उप-भाग के लिए सबसे दूर जोड़े को कंप्यूटिंग और तुलना करके सबसे दूरस्थ जोड़ों की गणना करता है, जो रूट के रूप में एक मनमानी नोड से शुरू होता है (पहले से ही किसी अन्य उत्तर में उल्लिखित)।