प्रत्येक नोड - एल्गोरिदम, ग्राफ, ग्राफ़-एल्गोरिदम से ग्राफ़ की गहराई को कुशलतापूर्वक पाएं

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

मैं कैसे कुशलता से एक बहुत बड़े ग्राफ की न्यूनतम गहराई का पता लगा सकता हूं। यह ध्यान देने योग्य है कि प्रश्न में ग्राफ है कोई चक्र नहीं.

उत्तर:

अप्रत्यक्ष पेड़ ग्राफ के ग्राफ केंद्र / केंद्र को खोजने के लिए:

1. सभी पत्ती नोड्स ओ (एन) की एक सूची खोजने के लिए डीएफएस करें
2. ग्राफ से इन सभी लीफ नोड्स को हटा दें और डिलीट के दौरान ध्यान दें कि कौन से नए नोड्स लीफ नोड्स बन जाते हैं
3. चरण 2 को तब तक दोहराएं जब तक कि ग्राफ पूरी तरह से हटा नहीं दिया जाता है

एल्गोरिथ्म के अंतिम चरण में हटाए गए नोड / नोड आपके पेड़ के ग्राफ केंद्र होंगे।

प्रत्येक नोड को एक बार हटा दिया जाता है, इसलिए यह पूरी प्रक्रिया O (n) में की जा सकती है।

आपको जो दिख रहा है वह है व्यास / 2. आप नीचे दिए गए पेड़ के व्यास की गणना कर सकते हैं और इसे कॉल कर सकते हैं findDiameter(n, null), एक मनमाना नोड के लिए n पेड़ का।

public findDiameter(node n, node from) returns <depth, diameter>

// apply recursively on all children
foreach child in (neighbors(n) minus from) do
<de, di> = findDiameter(child, n)

// depth of this node is 1 more than max depth of children
depth = 1 + max(de)

// max diameter either uses this node, then it is 1 + the 2 largest depths
// or it does not use this node, then it"s the max depth of the neighbors
diameter = max(max(di), 1 + max(de) + oneButLargest(de))

आपको बस इतना करना है कि पड़ोसी के सबसे बड़े व्यास और 2 सबसे बड़ी गहराई का ध्यान रखें।