ग्राफ में सबसे लंबा रास्ता कैसे खोजें?

Question

हम फार्म की एक संलग्नता सूची दी जाती है

U -> (U,V,C) -> (U,V,C) ... 
U2 -> ... 
U3 -> ... 
. 
. 
etc 

(U,V,C) वहाँ लागत सी

दिया संलग्नता सूची एन के साथ एक एकल जुड़ा पेड़ के लिए है के साथ यू से बढ़त वी के लिए इस प्रकार युक्त नोड्स का मतलब एन -1 किनारों।

नोड्स का एक सेट F=F1,F2,F3...Fk दिया गया है।

अब सवाल यह है कि एफ में नोड्स के बीच सबसे लंबा रास्ता खोजने का सबसे अच्छा तरीका क्या है? क्या ओ (एन) में ऐसा करना संभव है?

एफ में प्रत्येक नोड से डीएफएस एकमात्र विकल्प है?

Answer 1

मैं आपके प्रश्न को समझ गया क्योंकि सेट एफ से नोड्स की एक जोड़ी ढूंढने के लिए कहा गया है ताकि उन दो नोड्स के बीच अद्वितीय पथ जितना हो सके। पथ अद्वितीय है क्योंकि आपका ग्राफ एक पेड़ है।

समस्या एफ में प्रत्येक नोड से डीएफएस कर के रूप में आप का उल्लेख है, एक हे (nk) समाधान जहां n ग्राफ और कश्मीर के आकार है के लिए द्वारा तुच्छता से हल किया जा सकता सेट के आकार है एफ

हालांकि, आप विभाजन को संभावित रूप से तेज़ी से हल कर सकते हैं और दृष्टिकोण जीत सकते हैं। ग्राफ से किसी भी नोड आर को चुनें, और एक अन्य डीएफएस का उपयोग दूरी को दूर करने के लिए डिस्ट (आर, ए) को हर दूसरे नोड एए को सारणीबद्ध करने के लिए करें और उसी समय नोड्स को एस 1 को उप-विभाजन करने के लिए विभाजन करें ..., sm जहां m की संख्या है आर से किनारों; यही है, ये रूट पे पर लटक रहे मी पेड़ हैं। अब, किसी भी एफ और जी के लिए जो विभिन्न उप-नियमों से संबंधित है, यह मानता है कि उनके बीच का पथ जिला (आर, एफ) + जिस्ट (आर, जी) किनारों है, इसलिए ओ (के^2) समय में सबसे लंबे समय तक इस तरह के पथ की खोज करना संभव है। इसके अलावा, आप उपप्रब्लेम एस 1, ..., एसएम को उस मामले को कवर करने के लिए है जहां सबसे लंबा रास्ता उन पेड़ों में से एक के अंदर है। समग्र जटिलता ओ (एन के) से कम हो सकती है लेकिन पाठक को अभ्यास के रूप में गणित छोड़ दिया जाता है।

Answer 2

यदि मैं आपका प्रश्न सही ढंग से समझ गया, तो आप एक फैले पेड़ में सबसे लंबा लागत पथ खोजने की कोशिश कर रहे हैं।

आप एन

आप कदम नीचे करना चाहिए की बड़ी मूल्य के लिए सिर्फ 2 पूरा ट्रेवर्सल अर्थात हे (2N) ~ हे (एन) में पथ पा सकते हैं।

1. स्पैनिंग पेड़ में कोई भी नोड चुनें।
2. नोड से किसी भी अल्गो (डीएफएस या बीएफएस) चलाएं और इस नोड से सबसे लंबी लागत पथ पाएं।

यह आपके सबसे लंबे समय तक लागत वाला मार्ग नहीं होगा जैसा आपने यादृच्छिक रूप से नोड को चुनकर शुरू किया था।

सबसे लंबे समय तक लागत पथ कदम 2.
1. इस बार सबसे लंबे समय तक लागत पथ आपको मिल में पाया के अंतिम नोड से
2. भागो बीएफएस या डीएफएस एक बार और, सबसे लंबे समय तक हो जाएगा वृक्षारोपण पेड़ में पथ।

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